Skip to content

Commit 5d3f580

Browse files
rjl493456442rjl493456442
authored
trie: add node type common package (ethereum#27160)
* trie: add node type common package In trie/types package, a few node wrappers are defined, which will be used in both trie package, trie/snap package, etc. Therefore, a standalone common package is created to put these stuffs. * trie: rename trie/types to trie/trienode
1 parent b1113aa commit 5d3f580

File tree

7 files changed

+133
-116
lines changed

7 files changed

+133
-116
lines changed

‎trie/committer.go‎

Lines changed: 14 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -20,6 +20,7 @@ import (
2020
"fmt"
2121

2222
"github.com/ethereum/go-ethereum/common"
23+
"github.com/ethereum/go-ethereum/trie/trienode"
2324
)
2425

2526
// leaf represents a trie leaf node
@@ -33,13 +34,15 @@ type leaf struct {
3334
// insertion order.
3435
type committer struct {
3536
nodes *NodeSet
37+
tracer *tracer
3638
collectLeaf bool
3739
}
3840

3941
// newCommitter creates a new committer or picks one from the pool.
40-
func newCommitter(nodeset *NodeSet, collectLeaf bool) *committer {
42+
func newCommitter(nodeset *NodeSet, tracer *tracer, collectLeaf bool) *committer {
4143
return &committer{
4244
nodes: nodeset,
45+
tracer: tracer,
4346
collectLeaf: collectLeaf,
4447
}
4548
}
@@ -134,22 +137,22 @@ func (c *committer) store(path []byte, n node) node {
134137
// The node is embedded in its parent, in other words, this node
135138
// will not be stored in the database independently, mark it as
136139
// deleted only if the node was existent in database before.
137-
if _, ok := c.nodes.accessList[string(path)]; ok {
138-
c.nodes.markDeleted(path)
140+
prev, ok := c.tracer.accessList[string(path)]
141+
if ok {
142+
c.nodes.addNode(path, trienode.NewWithPrev(common.Hash{}, nil, prev))
139143
}
140144
return n
141145
}
142-
// We have the hash already, estimate the RLP encoding-size of the node.
143-
// The size is used for mem tracking, does not need to be exact
146+
// Collect the dirty node to nodeset for return.
144147
var (
145148
nhash = common.BytesToHash(hash)
146-
mnode = &memoryNode{
147-
hash: nhash,
148-
node: nodeToBytes(n),
149-
}
149+
node = trienode.NewWithPrev(
150+
nhash,
151+
nodeToBytes(n),
152+
c.tracer.accessList[string(path)],
153+
)
150154
)
151-
// Collect the dirty node to nodeset for return.
152-
c.nodes.markUpdated(path, mnode)
155+
c.nodes.addNode(path, node)
153156

154157
// Collect the corresponding leaf node if it's required. We don't check
155158
// full node since it's impossible to store value in fullNode. The key

‎trie/database.go‎

Lines changed: 4 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -31,6 +31,7 @@ import (
3131
"github.com/ethereum/go-ethereum/log"
3232
"github.com/ethereum/go-ethereum/metrics"
3333
"github.com/ethereum/go-ethereum/rlp"
34+
"github.com/ethereum/go-ethereum/trie/trienode"
3435
)
3536

3637
var (
@@ -607,11 +608,11 @@ func (db *Database) Update(nodes *MergedNodeSet) error {
607608
}
608609
for _, owner := range order {
609610
subset := nodes.sets[owner]
610-
subset.forEachWithOrder(func(path string, n *memoryNode) {
611-
if n.isDeleted() {
611+
subset.forEachWithOrder(func(path string, n *trienode.Node) {
612+
if n.IsDeleted() {
612613
return // ignore deletion
613614
}
614-
db.insert(n.hash, n.node)
615+
db.insert(n.Hash, n.Blob)
615616
})
616617
}
617618
// Link up the account trie and storage trie if the node points

‎trie/nodeset.go‎

Lines changed: 31 additions & 86 deletions
Original file line numberDiff line numberDiff line change
@@ -22,113 +22,59 @@ import (
2222
"strings"
2323

2424
"github.com/ethereum/go-ethereum/common"
25+
"github.com/ethereum/go-ethereum/trie/trienode"
2526
)
2627

27-
// memoryNode is all the information we know about a single cached trie node
28-
// in the memory.
29-
type memoryNode struct {
30-
hash common.Hash // Node hash by hashing node blob, empty for deleted nodes
31-
node []byte // Encoded node blob, nil for deleted nodes
32-
}
33-
34-
// memorySize returns the total memory size used by this node.
35-
// nolint:unused
36-
func (n *memoryNode) memorySize(pathlen int) int {
37-
return len(n.node) + common.HashLength + pathlen
38-
}
39-
40-
// rlp returns the raw rlp encoded blob of the cached trie node, either directly
41-
// from the cache, or by regenerating it from the collapsed node.
42-
// nolint:unused
43-
func (n *memoryNode) rlp() []byte {
44-
return n.node
45-
}
46-
47-
// obj returns the decoded and expanded trie node, either directly from the cache,
48-
// or by regenerating it from the rlp encoded blob.
49-
// nolint:unused
50-
func (n *memoryNode) obj() node {
51-
return mustDecodeNode(n.hash[:], n.node)
52-
}
53-
54-
// isDeleted returns the indicator if the node is marked as deleted.
55-
func (n *memoryNode) isDeleted() bool {
56-
return n.hash == (common.Hash{})
57-
}
58-
59-
// nodeWithPrev wraps the memoryNode with the previous node value.
60-
// nolint: unused
61-
type nodeWithPrev struct {
62-
*memoryNode
63-
prev []byte // RLP-encoded previous value, nil means it's non-existent
64-
}
65-
66-
// unwrap returns the internal memoryNode object.
67-
// nolint:unused
68-
func (n *nodeWithPrev) unwrap() *memoryNode {
69-
return n.memoryNode
70-
}
71-
72-
// memorySize returns the total memory size used by this node. It overloads
73-
// the function in memoryNode by counting the size of previous value as well.
74-
// nolint: unused
75-
func (n *nodeWithPrev) memorySize(pathlen int) int {
76-
return n.memoryNode.memorySize(pathlen) + len(n.prev)
77-
}
78-
7928
// NodeSet contains all dirty nodes collected during the commit operation.
8029
// Each node is keyed by path. It's not thread-safe to use.
8130
type NodeSet struct {
82-
owner common.Hash // the identifier of the trie
83-
nodes map[string]*memoryNode // the set of dirty nodes(inserted, updated, deleted)
84-
leaves []*leaf // the list of dirty leaves
85-
updates int // the count of updated and inserted nodes
86-
deletes int // the count of deleted nodes
87-
88-
// The list of accessed nodes, which records the original node value.
89-
// The origin value is expected to be nil for newly inserted node
90-
// and is expected to be non-nil for other types(updated, deleted).
91-
accessList map[string][]byte
31+
owner common.Hash // the identifier of the trie
32+
leaves []*leaf // the list of dirty leaves
33+
updates int // the count of updated and inserted nodes
34+
deletes int // the count of deleted nodes
35+
36+
// The set of all dirty nodes. Dirty nodes include newly inserted nodes,
37+
// deleted nodes and updated nodes. The original value of the newly
38+
// inserted node must be nil, and the original value of the other two
39+
// types must be non-nil.
40+
nodes map[string]*trienode.WithPrev
9241
}
9342

9443
// NewNodeSet initializes an empty node set to be used for tracking dirty nodes
9544
// from a specific account or storage trie. The owner is zero for the account
9645
// trie and the owning account address hash for storage tries.
97-
func NewNodeSet(owner common.Hash, accessList map[string][]byte) *NodeSet {
46+
func NewNodeSet(owner common.Hash) *NodeSet {
9847
return &NodeSet{
99-
owner: owner,
100-
nodes: make(map[string]*memoryNode),
101-
accessList: accessList,
48+
owner: owner,
49+
nodes: make(map[string]*trienode.WithPrev),
10250
}
10351
}
10452

10553
// forEachWithOrder iterates the dirty nodes with the order from bottom to top,
10654
// right to left, nodes with the longest path will be iterated first.
107-
func (set *NodeSet) forEachWithOrder(callback func(path string, n *memoryNode)) {
55+
func (set *NodeSet) forEachWithOrder(callback func(path string, n *trienode.Node)) {
10856
var paths sort.StringSlice
10957
for path := range set.nodes {
11058
paths = append(paths, path)
11159
}
11260
// Bottom-up, longest path first
11361
sort.Sort(sort.Reverse(paths))
11462
for _, path := range paths {
115-
callback(path, set.nodes[path])
63+
callback(path, set.nodes[path].Unwrap())
11664
}
11765
}
11866

119-
// markUpdated marks the node as dirty(newly-inserted or updated).
120-
func (set *NodeSet) markUpdated(path []byte, node *memoryNode) {
121-
set.nodes[string(path)] = node
122-
set.updates += 1
123-
}
124-
125-
// markDeleted marks the node as deleted.
126-
func (set *NodeSet) markDeleted(path []byte) {
127-
set.nodes[string(path)] = &memoryNode{}
128-
set.deletes += 1
67+
// addNode adds the provided dirty node into set.
68+
func (set *NodeSet) addNode(path []byte, n *trienode.WithPrev) {
69+
if n.IsDeleted() {
70+
set.deletes += 1
71+
} else {
72+
set.updates += 1
73+
}
74+
set.nodes[string(path)] = n
12975
}
13076

131-
// addLeaf collects the provided leaf node into set.
77+
// addLeaf adds the provided leaf node into set.
13278
func (set *NodeSet) addLeaf(node *leaf) {
13379
set.leaves = append(set.leaves, node)
13480
}
@@ -143,7 +89,7 @@ func (set *NodeSet) Size() (int, int) {
14389
func (set *NodeSet) Hashes() []common.Hash {
14490
var ret []common.Hash
14591
for _, node := range set.nodes {
146-
ret = append(ret, node.hash)
92+
ret = append(ret, node.Hash)
14793
}
14894
return ret
14995
}
@@ -155,18 +101,17 @@ func (set *NodeSet) Summary() string {
155101
if set.nodes != nil {
156102
for path, n := range set.nodes {
157103
// Deletion
158-
if n.isDeleted() {
159-
fmt.Fprintf(out, " [-]: %x prev: %x\n", path, set.accessList[path])
104+
if n.IsDeleted() {
105+
fmt.Fprintf(out, " [-]: %x prev: %x\n", path, n.Prev)
160106
continue
161107
}
162108
// Insertion
163-
origin, ok := set.accessList[path]
164-
if !ok {
165-
fmt.Fprintf(out, " [+]: %x -> %v\n", path, n.hash)
109+
if len(n.Prev) == 0 {
110+
fmt.Fprintf(out, " [+]: %x -> %v\n", path, n.Hash)
166111
continue
167112
}
168113
// Update
169-
fmt.Fprintf(out, " [*]: %x -> %v prev: %x\n", path, n.hash, origin)
114+
fmt.Fprintf(out, " [*]: %x -> %v prev: %x\n", path, n.Hash, n.Prev)
170115
}
171116
}
172117
for _, n := range set.leaves {

‎trie/tracer.go‎

Lines changed: 7 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -16,7 +16,10 @@
1616

1717
package trie
1818

19-
import "github.com/ethereum/go-ethereum/common"
19+
import (
20+
"github.com/ethereum/go-ethereum/common"
21+
"github.com/ethereum/go-ethereum/trie/trienode"
22+
)
2023

2124
// tracer tracks the changes of trie nodes. During the trie operations,
2225
// some nodes can be deleted from the trie, while these deleted nodes
@@ -117,9 +120,10 @@ func (t *tracer) markDeletions(set *NodeSet) {
117120
// It's possible a few deleted nodes were embedded
118121
// in their parent before, the deletions can be no
119122
// effect by deleting nothing, filter them out.
120-
if _, ok := set.accessList[path]; !ok {
123+
prev, ok := t.accessList[path]
124+
if !ok {
121125
continue
122126
}
123-
set.markDeleted([]byte(path))
127+
set.addNode([]byte(path), trienode.NewWithPrev(common.Hash{}, nil, prev))
124128
}
125129
}

‎trie/trie.go‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -574,7 +574,7 @@ func (t *Trie) Hash() common.Hash {
574574
func (t *Trie) Commit(collectLeaf bool) (common.Hash, *NodeSet) {
575575
defer t.tracer.reset()
576576

577-
nodes := NewNodeSet(t.owner, t.tracer.accessList)
577+
nodes := NewNodeSet(t.owner)
578578
t.tracer.markDeletions(nodes)
579579

580580
// Trie is empty and can be classified into two types of situations:
@@ -595,7 +595,7 @@ func (t *Trie) Commit(collectLeaf bool) (common.Hash, *NodeSet) {
595595
t.root = hashedNode
596596
return rootHash, nil
597597
}
598-
t.root = newCommitter(nodes, collectLeaf).Commit(t.root)
598+
t.root = newCommitter(nodes, t.tracer, collectLeaf).Commit(t.root)
599599
return rootHash, nodes
600600
}
601601

‎trie/trie_test.go‎

Lines changed: 8 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -408,39 +408,36 @@ func verifyAccessList(old *Trie, new *Trie, set *NodeSet) error {
408408
// Check insertion set
409409
for path := range inserts {
410410
n, ok := set.nodes[path]
411-
if !ok || n.isDeleted() {
411+
if !ok || n.IsDeleted() {
412412
return errors.New("expect new node")
413413
}
414-
_, ok = set.accessList[path]
415-
if ok {
414+
if len(n.Prev) > 0 {
416415
return errors.New("unexpected origin value")
417416
}
418417
}
419418
// Check deletion set
420419
for path, blob := range deletes {
421420
n, ok := set.nodes[path]
422-
if !ok || !n.isDeleted() {
421+
if !ok || !n.IsDeleted() {
423422
return errors.New("expect deleted node")
424423
}
425-
v, ok := set.accessList[path]
426-
if !ok {
424+
if len(n.Prev) == 0 {
427425
return errors.New("expect origin value")
428426
}
429-
if !bytes.Equal(v, blob) {
427+
if !bytes.Equal(n.Prev, blob) {
430428
return errors.New("invalid origin value")
431429
}
432430
}
433431
// Check update set
434432
for path, blob := range updates {
435433
n, ok := set.nodes[path]
436-
if !ok || n.isDeleted() {
434+
if !ok || n.IsDeleted() {
437435
return errors.New("expect updated node")
438436
}
439-
v, ok := set.accessList[path]
440-
if !ok {
437+
if len(n.Prev) == 0 {
441438
return errors.New("expect origin value")
442439
}
443-
if !bytes.Equal(v, blob) {
440+
if !bytes.Equal(n.Prev, blob) {
444441
return errors.New("invalid origin value")
445442
}
446443
}

0 commit comments

Comments
 (0)