2023-12-28 16:48:15 +08:00
|
|
|
package trie
|
|
|
|
|
|
|
|
import (
|
|
|
|
"bytes"
|
|
|
|
"errors"
|
|
|
|
"fmt"
|
|
|
|
"runtime"
|
2024-05-15 15:28:57 +08:00
|
|
|
"strings"
|
2023-12-28 16:48:15 +08:00
|
|
|
"sync"
|
|
|
|
"sync/atomic"
|
|
|
|
|
2024-01-22 14:29:14 +08:00
|
|
|
"time"
|
|
|
|
|
2023-12-28 16:48:15 +08:00
|
|
|
"github.com/ethereum/go-ethereum/common"
|
2024-05-15 15:28:57 +08:00
|
|
|
"github.com/ethereum/go-ethereum/common/mclock"
|
2024-03-08 15:36:25 +08:00
|
|
|
"github.com/ethereum/go-ethereum/ethdb"
|
2023-12-28 16:48:15 +08:00
|
|
|
"github.com/ethereum/go-ethereum/log"
|
|
|
|
"github.com/ethereum/go-ethereum/rlp"
|
2024-03-08 15:36:25 +08:00
|
|
|
"github.com/ethereum/go-ethereum/triedb/database"
|
2023-12-28 16:48:15 +08:00
|
|
|
"github.com/olekukonko/tablewriter"
|
2024-01-22 14:29:14 +08:00
|
|
|
|
|
|
|
"github.com/ethereum/go-ethereum/core/rawdb"
|
|
|
|
"github.com/ethereum/go-ethereum/core/types"
|
|
|
|
"golang.org/x/sync/semaphore"
|
2023-12-28 16:48:15 +08:00
|
|
|
)
|
|
|
|
|
2024-03-08 15:36:25 +08:00
|
|
|
type Database interface {
|
|
|
|
database.Database
|
|
|
|
Scheme() string
|
|
|
|
Cap(limit common.StorageSize) error
|
|
|
|
DiskDB() ethdb.Database
|
|
|
|
}
|
2024-05-15 15:28:57 +08:00
|
|
|
|
|
|
|
const TopN = 3
|
|
|
|
|
2023-12-28 16:48:15 +08:00
|
|
|
type Inspector struct {
|
2024-01-22 14:29:14 +08:00
|
|
|
trie *Trie // traverse trie
|
2024-03-08 15:36:25 +08:00
|
|
|
db Database
|
2024-01-22 14:29:14 +08:00
|
|
|
stateRootHash common.Hash
|
2024-05-15 15:28:57 +08:00
|
|
|
blockNum uint64
|
2024-01-22 14:29:14 +08:00
|
|
|
root node // root of triedb
|
|
|
|
sem *semaphore.Weighted
|
|
|
|
eoaAccountNums uint64
|
2024-05-15 15:28:57 +08:00
|
|
|
|
|
|
|
wg sync.WaitGroup
|
|
|
|
|
|
|
|
results stat
|
|
|
|
topN int
|
|
|
|
|
|
|
|
totalAccountNum atomic.Uint64
|
|
|
|
totalStorageNum atomic.Uint64
|
|
|
|
lastTime mclock.AbsTime
|
|
|
|
}
|
|
|
|
|
|
|
|
type stat struct {
|
|
|
|
lock sync.RWMutex
|
|
|
|
account *trieStat
|
|
|
|
storageTopN []*trieStat
|
|
|
|
storageTopNTotal []uint64
|
|
|
|
storageTotal nodeStat
|
|
|
|
storageTrieNum uint64
|
2023-12-28 16:48:15 +08:00
|
|
|
}
|
|
|
|
|
2024-05-15 15:28:57 +08:00
|
|
|
type trieStat struct {
|
|
|
|
owner common.Hash
|
|
|
|
totalNodeStat nodeStat
|
|
|
|
nodeStatByLevel [16]nodeStat
|
2023-12-28 16:48:15 +08:00
|
|
|
}
|
|
|
|
|
2024-05-15 15:28:57 +08:00
|
|
|
type nodeStat struct {
|
|
|
|
ShortNodeCnt atomic.Uint64
|
|
|
|
FullNodeCnt atomic.Uint64
|
|
|
|
ValueNodeCnt atomic.Uint64
|
|
|
|
}
|
|
|
|
|
|
|
|
func (ns *nodeStat) IsEmpty() bool {
|
|
|
|
if ns.FullNodeCnt.Load() == 0 && ns.ShortNodeCnt.Load() == 0 && ns.ValueNodeCnt.Load() == 0 {
|
|
|
|
return true
|
|
|
|
}
|
|
|
|
return false
|
|
|
|
}
|
|
|
|
|
|
|
|
func (s *stat) add(ts *trieStat, topN int) {
|
|
|
|
s.lock.Lock()
|
|
|
|
defer s.lock.Unlock()
|
|
|
|
if ts.owner == (common.Hash{}) {
|
|
|
|
s.account = ts
|
|
|
|
return
|
|
|
|
}
|
|
|
|
|
|
|
|
total := ts.totalNodeStat.ValueNodeCnt.Load() + ts.totalNodeStat.FullNodeCnt.Load() + ts.totalNodeStat.ShortNodeCnt.Load()
|
|
|
|
if len(s.storageTopNTotal) == 0 || total > s.storageTopNTotal[len(s.storageTopNTotal)-1] {
|
|
|
|
var (
|
|
|
|
i int
|
|
|
|
t uint64
|
|
|
|
)
|
|
|
|
for i, t = range s.storageTopNTotal {
|
|
|
|
if total < t {
|
|
|
|
continue
|
|
|
|
}
|
|
|
|
break
|
|
|
|
}
|
|
|
|
s.storageTopNTotal = append(s.storageTopNTotal[:i], append([]uint64{total}, s.storageTopNTotal[i:]...)...)
|
|
|
|
s.storageTopN = append(s.storageTopN[:i], append([]*trieStat{ts}, s.storageTopN[i:]...)...)
|
|
|
|
if len(s.storageTopN) > topN {
|
|
|
|
s.storageTopNTotal = s.storageTopNTotal[:topN]
|
|
|
|
s.storageTopN = s.storageTopN[:topN]
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
|
|
|
s.storageTotal.ShortNodeCnt.Add(ts.totalNodeStat.ShortNodeCnt.Load())
|
|
|
|
s.storageTotal.ValueNodeCnt.Add(ts.totalNodeStat.ValueNodeCnt.Load())
|
|
|
|
s.storageTotal.FullNodeCnt.Add(ts.totalNodeStat.FullNodeCnt.Load())
|
|
|
|
s.storageTrieNum++
|
2023-12-28 16:48:15 +08:00
|
|
|
}
|
|
|
|
|
2024-05-15 15:28:57 +08:00
|
|
|
func (trieStat *trieStat) add(theNode node, height int) {
|
2023-12-28 16:48:15 +08:00
|
|
|
switch (theNode).(type) {
|
|
|
|
case *shortNode:
|
2024-05-15 15:28:57 +08:00
|
|
|
trieStat.totalNodeStat.ShortNodeCnt.Add(1)
|
|
|
|
trieStat.nodeStatByLevel[height].ShortNodeCnt.Add(1)
|
2023-12-28 16:48:15 +08:00
|
|
|
case *fullNode:
|
2024-05-15 15:28:57 +08:00
|
|
|
trieStat.totalNodeStat.FullNodeCnt.Add(1)
|
|
|
|
trieStat.nodeStatByLevel[height].FullNodeCnt.Add(1)
|
2023-12-28 16:48:15 +08:00
|
|
|
case valueNode:
|
2024-05-15 15:28:57 +08:00
|
|
|
trieStat.totalNodeStat.ValueNodeCnt.Add(1)
|
|
|
|
trieStat.nodeStatByLevel[height].ValueNodeCnt.Add(1)
|
2023-12-28 16:48:15 +08:00
|
|
|
}
|
|
|
|
}
|
|
|
|
|
2024-05-15 15:28:57 +08:00
|
|
|
func (trieStat *trieStat) Display(ownerAddress string, treeType string) string {
|
|
|
|
sw := new(strings.Builder)
|
|
|
|
table := tablewriter.NewWriter(sw)
|
2023-12-28 16:48:15 +08:00
|
|
|
table.SetHeader([]string{"-", "Level", "ShortNodeCnt", "FullNodeCnt", "ValueNodeCnt"})
|
|
|
|
if ownerAddress == "" {
|
|
|
|
table.SetCaption(true, fmt.Sprintf("%v", treeType))
|
|
|
|
} else {
|
|
|
|
table.SetCaption(true, fmt.Sprintf("%v-%v", treeType, ownerAddress))
|
|
|
|
}
|
|
|
|
table.SetAlignment(1)
|
2024-05-15 15:28:57 +08:00
|
|
|
|
|
|
|
for i := range trieStat.nodeStatByLevel {
|
|
|
|
if trieStat.nodeStatByLevel[i].IsEmpty() {
|
|
|
|
continue
|
2023-12-28 16:48:15 +08:00
|
|
|
}
|
|
|
|
table.AppendBulk([][]string{
|
2024-05-15 15:28:57 +08:00
|
|
|
{"-", fmt.Sprintf("%d", i),
|
|
|
|
fmt.Sprintf("%d", trieStat.nodeStatByLevel[i].ShortNodeCnt.Load()),
|
|
|
|
fmt.Sprintf("%d", trieStat.nodeStatByLevel[i].FullNodeCnt.Load()),
|
|
|
|
fmt.Sprintf("%d", trieStat.nodeStatByLevel[i].ValueNodeCnt.Load())},
|
2023-12-28 16:48:15 +08:00
|
|
|
})
|
|
|
|
}
|
|
|
|
table.AppendBulk([][]string{
|
2024-05-15 15:28:57 +08:00
|
|
|
{"Total", "-", fmt.Sprintf("%d", trieStat.totalNodeStat.ShortNodeCnt.Load()), fmt.Sprintf("%d", trieStat.totalNodeStat.FullNodeCnt.Load()), fmt.Sprintf("%d", trieStat.totalNodeStat.ValueNodeCnt.Load())},
|
2023-12-28 16:48:15 +08:00
|
|
|
})
|
|
|
|
table.Render()
|
2024-05-15 15:28:57 +08:00
|
|
|
return sw.String()
|
2023-12-28 16:48:15 +08:00
|
|
|
}
|
|
|
|
|
|
|
|
// NewInspector return a inspector obj
|
2024-05-15 15:28:57 +08:00
|
|
|
func NewInspector(tr *Trie, db Database, stateRootHash common.Hash, blockNum uint64, jobNum uint64, topN int) (*Inspector, error) {
|
2023-12-28 16:48:15 +08:00
|
|
|
if tr == nil {
|
|
|
|
return nil, errors.New("trie is nil")
|
|
|
|
}
|
|
|
|
|
|
|
|
if tr.root == nil {
|
|
|
|
return nil, errors.New("trie root is nil")
|
|
|
|
}
|
|
|
|
|
|
|
|
ins := &Inspector{
|
2024-05-15 15:28:57 +08:00
|
|
|
trie: tr,
|
|
|
|
db: db,
|
|
|
|
stateRootHash: stateRootHash,
|
|
|
|
blockNum: blockNum,
|
|
|
|
root: tr.root,
|
|
|
|
results: stat{},
|
|
|
|
topN: topN,
|
|
|
|
totalAccountNum: atomic.Uint64{},
|
|
|
|
totalStorageNum: atomic.Uint64{},
|
|
|
|
lastTime: mclock.Now(),
|
|
|
|
sem: semaphore.NewWeighted(int64(jobNum)),
|
|
|
|
|
|
|
|
wg: sync.WaitGroup{},
|
|
|
|
|
2024-01-22 14:29:14 +08:00
|
|
|
eoaAccountNums: 0,
|
2023-12-28 16:48:15 +08:00
|
|
|
}
|
|
|
|
|
|
|
|
return ins, nil
|
|
|
|
}
|
|
|
|
|
|
|
|
// Run statistics, external call
|
2024-05-15 15:28:57 +08:00
|
|
|
func (s *Inspector) Run() {
|
|
|
|
ticker := time.NewTicker(30 * time.Second)
|
|
|
|
go func() {
|
|
|
|
defer ticker.Stop()
|
|
|
|
for range ticker.C {
|
|
|
|
if s.db.Scheme() == rawdb.HashScheme {
|
|
|
|
s.db.Cap(DEFAULT_TRIEDBCACHE_SIZE)
|
2024-01-22 14:29:14 +08:00
|
|
|
}
|
2024-05-15 15:28:57 +08:00
|
|
|
runtime.GC()
|
|
|
|
}
|
|
|
|
}()
|
2023-12-28 16:48:15 +08:00
|
|
|
|
2024-05-15 15:28:57 +08:00
|
|
|
log.Info("Find Account Trie Tree", "rootHash: ", s.trie.Hash().String(), "BlockNum: ", s.blockNum)
|
2023-12-28 16:48:15 +08:00
|
|
|
|
2024-05-15 15:28:57 +08:00
|
|
|
ts := &trieStat{
|
|
|
|
owner: common.Hash{},
|
2023-12-28 16:48:15 +08:00
|
|
|
}
|
2024-05-15 15:28:57 +08:00
|
|
|
s.traversal(s.trie, ts, s.root, 0, []byte{})
|
|
|
|
s.results.add(ts, s.topN)
|
|
|
|
s.wg.Wait()
|
|
|
|
}
|
2023-12-28 16:48:15 +08:00
|
|
|
|
2024-05-15 15:28:57 +08:00
|
|
|
func (s *Inspector) traversal(trie *Trie, ts *trieStat, n node, height int, path []byte) {
|
2023-12-28 16:48:15 +08:00
|
|
|
// nil node
|
2024-05-15 15:28:57 +08:00
|
|
|
if n == nil {
|
2023-12-28 16:48:15 +08:00
|
|
|
return
|
|
|
|
}
|
|
|
|
|
2024-05-15 15:28:57 +08:00
|
|
|
ts.add(n, height)
|
|
|
|
|
|
|
|
switch current := (n).(type) {
|
2023-12-28 16:48:15 +08:00
|
|
|
case *shortNode:
|
2024-05-15 15:28:57 +08:00
|
|
|
s.traversal(trie, ts, current.Val, height, append(path, current.Key...))
|
2023-12-28 16:48:15 +08:00
|
|
|
case *fullNode:
|
|
|
|
for idx, child := range current.Children {
|
|
|
|
if child == nil {
|
|
|
|
continue
|
|
|
|
}
|
2024-05-15 15:28:57 +08:00
|
|
|
p := common.CopyBytes(append(path, byte(idx)))
|
|
|
|
s.traversal(trie, ts, child, height+1, p)
|
2023-12-28 16:48:15 +08:00
|
|
|
}
|
|
|
|
case hashNode:
|
2024-05-15 15:28:57 +08:00
|
|
|
tn, err := trie.resloveWithoutTrack(current, path)
|
2023-12-28 16:48:15 +08:00
|
|
|
if err != nil {
|
2024-05-15 15:28:57 +08:00
|
|
|
fmt.Printf("Resolve HashNode error: %v, TrieRoot: %v, Height: %v, Path: %v\n", err, trie.Hash().String(), height+1, path)
|
2023-12-28 16:48:15 +08:00
|
|
|
return
|
|
|
|
}
|
2024-05-15 15:28:57 +08:00
|
|
|
s.PrintProgress(trie)
|
|
|
|
s.traversal(trie, ts, tn, height, path)
|
2023-12-28 16:48:15 +08:00
|
|
|
case valueNode:
|
|
|
|
if !hasTerm(path) {
|
|
|
|
break
|
|
|
|
}
|
2024-05-15 15:28:57 +08:00
|
|
|
var account types.StateAccount
|
2023-12-28 16:48:15 +08:00
|
|
|
if err := rlp.Decode(bytes.NewReader(current), &account); err != nil {
|
|
|
|
break
|
|
|
|
}
|
2024-01-22 14:29:14 +08:00
|
|
|
if common.BytesToHash(account.CodeHash) == types.EmptyCodeHash {
|
2024-05-15 15:28:57 +08:00
|
|
|
s.eoaAccountNums++
|
2024-01-22 14:29:14 +08:00
|
|
|
}
|
|
|
|
if account.Root == (common.Hash{}) || account.Root == types.EmptyRootHash {
|
2023-12-28 16:48:15 +08:00
|
|
|
break
|
|
|
|
}
|
|
|
|
ownerAddress := common.BytesToHash(hexToCompact(path))
|
2024-05-15 15:28:57 +08:00
|
|
|
contractTrie, err := New(StorageTrieID(s.stateRootHash, ownerAddress, account.Root), s.db)
|
2023-12-28 16:48:15 +08:00
|
|
|
if err != nil {
|
2024-05-15 15:28:57 +08:00
|
|
|
panic(err)
|
2023-12-28 16:48:15 +08:00
|
|
|
}
|
2024-01-22 14:29:14 +08:00
|
|
|
contractTrie.tracer.reset()
|
2023-12-28 16:48:15 +08:00
|
|
|
|
2024-05-15 15:28:57 +08:00
|
|
|
if s.sem.TryAcquire(1) {
|
|
|
|
s.wg.Add(1)
|
|
|
|
go func() {
|
|
|
|
t := &trieStat{
|
|
|
|
owner: ownerAddress,
|
|
|
|
}
|
|
|
|
s.traversal(contractTrie, t, contractTrie.root, 0, []byte{})
|
|
|
|
s.results.add(t, s.topN)
|
|
|
|
s.sem.Release(1)
|
|
|
|
s.wg.Done()
|
|
|
|
}()
|
|
|
|
} else {
|
|
|
|
t := &trieStat{
|
|
|
|
owner: ownerAddress,
|
|
|
|
}
|
|
|
|
s.traversal(contractTrie, t, contractTrie.root, 0, []byte{})
|
|
|
|
s.results.add(t, s.topN)
|
2023-12-28 16:48:15 +08:00
|
|
|
}
|
|
|
|
default:
|
2024-05-15 15:28:57 +08:00
|
|
|
panic(errors.New("invalid node type to traverse"))
|
2023-12-28 16:48:15 +08:00
|
|
|
}
|
|
|
|
}
|
|
|
|
|
2024-05-15 15:28:57 +08:00
|
|
|
func (s *Inspector) PrintProgress(t *Trie) {
|
|
|
|
var (
|
|
|
|
elapsed = mclock.Now().Sub(s.lastTime)
|
|
|
|
)
|
|
|
|
if t.owner == (common.Hash{}) {
|
|
|
|
s.totalAccountNum.Add(1)
|
|
|
|
} else {
|
|
|
|
s.totalStorageNum.Add(1)
|
2023-12-28 16:48:15 +08:00
|
|
|
}
|
2024-05-15 15:28:57 +08:00
|
|
|
if elapsed > 4*time.Second {
|
|
|
|
log.Info("traversal progress", "TotalAccountNum", s.totalAccountNum.Load(), "TotalStorageNum", s.totalStorageNum.Load(), "Goroutine", runtime.NumGoroutine())
|
|
|
|
s.lastTime = mclock.Now()
|
2023-12-28 16:48:15 +08:00
|
|
|
}
|
2024-05-15 15:28:57 +08:00
|
|
|
}
|
2023-12-28 16:48:15 +08:00
|
|
|
|
2024-05-15 15:28:57 +08:00
|
|
|
func (s *Inspector) DisplayResult() {
|
|
|
|
// display root hash
|
|
|
|
fmt.Println(s.results.account.Display("", "AccountTrie"))
|
|
|
|
fmt.Println("EOA accounts num: ", s.eoaAccountNums)
|
|
|
|
|
|
|
|
// display contract trie
|
|
|
|
for _, st := range s.results.storageTopN {
|
|
|
|
fmt.Println(st.Display(st.owner.String(), "StorageTrie"))
|
2023-12-28 16:48:15 +08:00
|
|
|
}
|
|
|
|
fmt.Printf("Contract Trie, total trie num: %v, ShortNodeCnt: %v, FullNodeCnt: %v, ValueNodeCnt: %v\n",
|
2024-05-15 15:28:57 +08:00
|
|
|
s.results.storageTrieNum, s.results.storageTotal.ShortNodeCnt.Load(), s.results.storageTotal.FullNodeCnt.Load(), s.results.storageTotal.ValueNodeCnt.Load())
|
2023-12-28 16:48:15 +08:00
|
|
|
}
|