blockstm

package module
v0.0.0-...-728847f Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Dec 20, 2024 License: Apache-2.0 Imports: 27 Imported by: 0

README

blockstm-go

General Block-STM execution engine for EVM in Go

Features

  • Block-STM with lazy update.
  • Minimize state synchronization overheads.
  • Optimized concurrent data structures.
  • Support optional DAG for full nodes to sync from sequencer faster.
  • Support any executor.

Libraries

  • Use hashmap for type-safe lock-free thread-safe concurrent map.
  • Use gpq for concurrent safe priority queue.

TODOs

  • Use atomic index to manage validation and execution tasks.
  • Implement an EVM executor task.
  • Test real mainnet blocks, and validate the results.
  • Benchmarks between parallel and sequential execution.
  • Profiling and optimizations.

Documentation

Index

Constants

View Source 
const (
	MVReadResultDone       = 0
	MVReadResultDependency = 1
	MVReadResultNone       = 2
)
View Source 
const (
	ReadKindMap     = 0
	ReadKindStorage = 1
)
View Source 
const BalancePath = 1
View Source 
const CodePath = 3
View Source 
const FlagDone = 0
View Source 
const FlagEstimate = 1
View Source 
const KeyLength = common.AddressLength + common.HashLength + 2
View Source 
const NoncePath = 2
View Source 
const SuicidePath = 4

Variables

This section is empty.

Functions

func GetDep 

func GetDep(deps TxnInputOutput) map[int]map[int]bool

func HasReadDep 

func HasReadDep(txFrom TxnOutput, txTo TxnInput) bool

func NewEVMTxContext 

func NewEVMTxContext(msg *core.Message) vm.TxContext

NewEVMTxContext creates a new transaction context for a single transaction.

func UpdateDeps 

func UpdateDeps(deps map[int]map[int]bool, t TxDep) map[int]map[int]bool

func ValidateVersion 

func ValidateVersion(txIdx int, lastInputOutput *TxnInputOutput, versionedData *MVHashMap) (valid bool)

Types

type DAG 

type DAG struct {
	*dag.DAG
}

func BuildDAG 

func BuildDAG(deps TxnInputOutput) (d DAG)

func (DAG) LongestPath 

func (d DAG) LongestPath(stats *hashmap.Map[int, ExecutionStat]) ([]int, uint64)

Find the longest execution path in the DAG

func (DAG) Report 

func (d DAG) Report(stats *hashmap.Map[int, ExecutionStat], out func(string))

type ErrExecAbortError 

type ErrExecAbortError struct {
	Dependency  int
	OriginError error
}

func (ErrExecAbortError) Error 

func (e ErrExecAbortError) Error() string

type ExecResult 

type ExecResult struct {
	// contains filtered or unexported fields
}

type ExecTask 

type ExecTask interface {
	Execute(mvh *MVHashMap, incarnation int) error
	MVReadList() []ReadDescriptor
	MVWriteList() []WriteDescriptor
	MVFullWriteList() []WriteDescriptor
	Hash() common.Hash
	Sender() common.Address
	Settle()
	Dependencies() []int
}

type ExecVersionView 

type ExecVersionView struct {
	// contains filtered or unexported fields
}

func (*ExecVersionView) Execute 

func (ev *ExecVersionView) Execute() (er ExecResult)

type ExecutionStat 

type ExecutionStat struct {
	TxIdx       int
	Incarnation int
	Start       uint64
	End         uint64
	Worker      int
}

type ExecutionTask 

type ExecutionTask struct {
	// contains filtered or unexported fields
}

func (*ExecutionTask) Dependencies 

func (task *ExecutionTask) Dependencies() []int

func (*ExecutionTask) Execute 

func (task *ExecutionTask) Execute(mvh *MVHashMap, incarnation int) (err error)

func (*ExecutionTask) Hash 

func (task *ExecutionTask) Hash() common.Hash

func (*ExecutionTask) MVFullWriteList 

func (task *ExecutionTask) MVFullWriteList() []WriteDescriptor

func (*ExecutionTask) MVReadList 

func (task *ExecutionTask) MVReadList() []ReadDescriptor

func (*ExecutionTask) MVWriteList 

func (task *ExecutionTask) MVWriteList() []WriteDescriptor

func (*ExecutionTask) Sender 

func (task *ExecutionTask) Sender() common.Address

func (*ExecutionTask) Settle 

func (task *ExecutionTask) Settle()

type IntHeap 

type IntHeap []int

func (IntHeap) Len 

func (h IntHeap) Len() int

func (IntHeap) Less 

func (h IntHeap) Less(i, j int) bool

func (*IntHeap) Pop 

func (h *IntHeap) Pop() any

func (*IntHeap) Push 

func (h *IntHeap) Push(x any)

func (IntHeap) Swap 

func (h IntHeap) Swap(i, j int)

type Key 

type Key [KeyLength]byte

func NewAddressKey 

func NewAddressKey(addr common.Address) Key

func NewStateKey 

func NewStateKey(addr common.Address, hash common.Hash) Key

func NewSubpathKey 

func NewSubpathKey(addr common.Address, subpath byte) Key

func (Key) GetAddress 

func (k Key) GetAddress() common.Address

func (Key) GetStateKey 

func (k Key) GetStateKey() common.Hash

func (Key) GetSubpath 

func (k Key) GetSubpath() byte

func (Key) IsAddress 

func (k Key) IsAddress() bool

func (Key) IsState 

func (k Key) IsState() bool

func (Key) IsSubpath 

func (k Key) IsSubpath() bool

type MVHashMap 

type MVHashMap struct {
	// contains filtered or unexported fields
}

func MakeMVHashMap 

func MakeMVHashMap() *MVHashMap

func (*MVHashMap) Delete 

func (mv *MVHashMap) Delete(k Key, txIdx int)

func (*MVHashMap) FlushMVWriteSet 

func (mv *MVHashMap) FlushMVWriteSet(writes []WriteDescriptor)

func (*MVHashMap) MarkEstimate 

func (mv *MVHashMap) MarkEstimate(k Key, txIdx int)

func (*MVHashMap) Read 

func (mv *MVHashMap) Read(k Key, txIdx int) (res MVReadResult)

func (*MVHashMap) ReadStorage 

func (mv *MVHashMap) ReadStorage(k Key, fallBack func() any) any

func (*MVHashMap) Write 

func (mv *MVHashMap) Write(k Key, v Version, data interface{})

type MVReadResult 

type MVReadResult struct {
	// contains filtered or unexported fields
}

func (*MVReadResult) DepIdx 

func (res *MVReadResult) DepIdx() int

func (*MVReadResult) Incarnation 

func (res *MVReadResult) Incarnation() int

func (MVReadResult) Status 

func (res MVReadResult) Status() int

func (*MVReadResult) Value 

func (res *MVReadResult) Value() interface{}

type MvCache 

type MvCache struct {
	// contains filtered or unexported fields
}

func (*MvCache) ClearReadMap 

func (m *MvCache) ClearReadMap()

func (*MvCache) ClearWriteMap 

func (m *MvCache) ClearWriteMap()

func (*MvCache) DepTxIndex 

func (m *MvCache) DepTxIndex() int

func (*MvCache) GetMVHashmap 

func (m *MvCache) GetMVHashmap() *MVHashMap

func (*MvCache) HadInvalidRead 

func (m *MvCache) HadInvalidRead() bool

func (*MvCache) MVFullWriteList 

func (m *MvCache) MVFullWriteList() []WriteDescriptor

func (*MvCache) MVReadList 

func (m *MvCache) MVReadList() []ReadDescriptor

func (*MvCache) MVReadMap 

func (m *MvCache) MVReadMap() map[Key]ReadDescriptor

func (*MvCache) MVWriteList 

func (m *MvCache) MVWriteList() []WriteDescriptor

func (*MvCache) SetIncarnation 

func (m *MvCache) SetIncarnation(inc int)

func (*MvCache) SetMVHashmap 

func (m *MvCache) SetMVHashmap(mvhm *MVHashMap)

type ParallelExecFailedError 

type ParallelExecFailedError struct {
	Msg string
}

func (ParallelExecFailedError) Error 

func (e ParallelExecFailedError) Error() string

type ParallelExecutionResult 

type ParallelExecutionResult struct {
	TxIO    *TxnInputOutput
	Stats   *hashmap.Map[int, ExecutionStat] // map[int]ExecutionStat
	Deps    *DAG
	AllDeps map[int]map[int]bool
}

func ExecuteParallel 

func ExecuteParallel(interruptCtx context.Context, tasks []ExecTask, profile bool, metadata bool, numProcs int) (result ParallelExecutionResult, err error)

type ParallelExecutor 

type ParallelExecutor struct {
	// contains filtered or unexported fields
}

func NewParallelExecutor 

func NewParallelExecutor(tasks []ExecTask, profile bool, metadata bool, numProcs int) *ParallelExecutor

func (*ParallelExecutor) Close 

func (pe *ParallelExecutor) Close(wait bool)

func (*ParallelExecutor) Prepare 

func (pe *ParallelExecutor) Prepare() error

nolint: gocognit

func (*ParallelExecutor) Step 

func (pe *ParallelExecutor) Step(res *ExecResult) (result ParallelExecutionResult, err error)

nolint: gocognit

type ParallelStateProcessor 

type ParallelStateProcessor struct {
	// contains filtered or unexported fields
}

ParallelBlockExecutor executes a block serially.

func NewParallelStateProcessor 

func NewParallelStateProcessor(config *params.ChainConfig, chain *core.HeaderChain, parallelProcesses int) *ParallelStateProcessor

NewParallelBlockExecutor creates a new ParallelBlockExecutor.

func (*ParallelStateProcessor) Process 

func (exec *ParallelStateProcessor) Process(block *types.Block, statedb *state.StateDB, cfg vm.Config) (*core.ProcessResult, error)

Process executes a block serially.

type PropertyCheck 

type PropertyCheck func(*ParallelExecutor) error

type ReadDescriptor 

type ReadDescriptor struct {
	Path Key
	Kind int
	V    Version
}

type SafeFIFOQueue 

type SafeFIFOQueue[d any] struct {
	// contains filtered or unexported fields
}

func NewSafeFIFOQueue 

func NewSafeFIFOQueue[d any](capacity int) *SafeFIFOQueue[d]

func (*SafeFIFOQueue[d]) Len 

func (q *SafeFIFOQueue[d]) Len() int

func (*SafeFIFOQueue[d]) Pop 

func (q *SafeFIFOQueue[d]) Pop() d

func (*SafeFIFOQueue[d]) Push 

func (q *SafeFIFOQueue[d]) Push(_ int, data d)

type SafePriorityQueue 

type SafePriorityQueue[d any] struct {
	// contains filtered or unexported fields
}

A thread safe priority queue

func NewSafePriorityQueue 

func NewSafePriorityQueue[d any](capacity int) *SafePriorityQueue[d]

func (*SafePriorityQueue[d]) Len 

func (pq *SafePriorityQueue[d]) Len() int

func (*SafePriorityQueue[d]) Pop 

func (pq *SafePriorityQueue[d]) Pop() d

func (*SafePriorityQueue[d]) Push 

func (pq *SafePriorityQueue[d]) Push(v int, data d)

type SafeQueue 

type SafeQueue[d any] interface {
	Push(v int, data d)
	Pop() d
	Len() int
}

type Scheduler 

type Scheduler struct {
	// contains filtered or unexported fields
}

func NewScheduler 

func NewScheduler(tasks []ExecTask) *Scheduler

type StatelessExecutor 

type StatelessExecutor struct {
	// contains filtered or unexported fields
}

func NewStatelessExecutor 

func NewStatelessExecutor(config *params.ChainConfig, block *types.Block, witness *stateless.Witness) *StatelessExecutor

func (*StatelessExecutor) Process 

func (exec *StatelessExecutor) Process(parallel bool) (common.Hash, common.Hash, error)

type TxDep 

type TxDep struct {
	Index         int
	ReadList      []ReadDescriptor
	FullWriteList [][]WriteDescriptor
}

type TxnIndexCells 

type TxnIndexCells struct {
	// contains filtered or unexported fields
}

type TxnInput 

type TxnInput []ReadDescriptor

type TxnInputOutput 

type TxnInputOutput struct {
	// contains filtered or unexported fields
}

func MakeTxnInputOutput 

func MakeTxnInputOutput(numTx int) *TxnInputOutput

func (*TxnInputOutput) AllWriteSet 

func (io *TxnInputOutput) AllWriteSet(txnIdx int) []WriteDescriptor

func (*TxnInputOutput) HasWritten 

func (io *TxnInputOutput) HasWritten(txnIdx int, k Key) bool

func (*TxnInputOutput) ReadSet 

func (io *TxnInputOutput) ReadSet(txnIdx int) []ReadDescriptor

func (*TxnInputOutput) RecordAllWriteAtOnce 

func (io *TxnInputOutput) RecordAllWriteAtOnce(outputs [][]WriteDescriptor)

func (*TxnInputOutput) RecordReadAtOnce 

func (io *TxnInputOutput) RecordReadAtOnce(inputs [][]ReadDescriptor)

func (*TxnInputOutput) WriteSet 

func (io *TxnInputOutput) WriteSet(txnIdx int) []WriteDescriptor

type TxnOutput 

type TxnOutput []WriteDescriptor

type Version 

type Version struct {
	TxnIndex    int
	Incarnation int
}

type WriteCell 

type WriteCell struct {
	// contains filtered or unexported fields
}

type WriteDescriptor 

type WriteDescriptor struct {
	Path Key
	V    Version
	Val  interface{}
}

Source Files

View all Source files

Directories

Path Synopsis
cmd
fetch-block

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.