blockstm

package
v0.0.2-tenderly Latest Latest
Warning

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

 Go to latest Published: Mar 23, 2026 License: GPL-3.0, LGPL-3.0 Imports: 14 Imported by: 0

Documentation

Index

Constants

View Source 
const (
	MVReadResultDone       = 0
	MVReadResultDependency = 1
	MVReadResultNone       = 2
)
View Source 
const (
	ReadKindMap     = 0
	ReadKindStorage = 1
)
View Source 
const FlagDone = 0
View Source 
const FlagEstimate = 1
View Source 
const KeyLength = common.AddressLength + common.HashLength + 2

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

HasReadDep checks if there are any read dependencies between two transactions. Performance optimization: Based on production metrics showing ~3M calls with median size of 15 and 95th percentile of 94, we avoid map allocation for small inputs. This optimization leverages the fact that for small lists, linear search is faster than map construction due to avoiding allocation overhead and better cache locality.

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 map[int]ExecutionStat) ([]int, uint64)

Find the longest execution path in the DAG

func (DAG) Report 

func (d DAG) Report(stats map[int]ExecutionStat, out func(string))

type DepsBuilder 

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

DepsBuilder builds a transitive-reduced dependency DAG incrementally. Uses an inverted index (key → latest writer) for O(R) dependency lookups per tx, and bitsets for O(N/64) transitive reduction via word-parallel set operations. Transactions must be added in sequential order (0, 1, 2, ...).

func NewDepsBuilder 

func NewDepsBuilder() *DepsBuilder

func (*DepsBuilder) AddTransaction 

func (db *DepsBuilder) AddTransaction(index int, readList []ReadDescriptor, writeList []WriteDescriptor) error

AddTransaction records a transaction's read/write sets and computes its reduced dependency set. Must be called with sequential indices (0, 1, 2, ...).

func (*DepsBuilder) GetDeps 

func (db *DepsBuilder) GetDeps() map[int]map[int]bool

GetDeps returns the reduced dependency graph as a map for backward compatibility with the existing serialization path. Returns nil if the builder encountered an error.

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 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 ParallelExecFailedError 

type ParallelExecFailedError struct {
	Msg string
}

func (ParallelExecFailedError) Error 

func (e ParallelExecFailedError) Error() string

type ParallelExecutionResult 

type ParallelExecutionResult struct {
	TxIO    *TxnInputOutput
	Stats   *map[int]ExecutionStat
	Deps    *DAG
	AllDeps map[int]map[int]bool
}

func ExecuteParallel 

func ExecuteParallel(tasks []ExecTask, profile bool, metadata bool, numProcs int, interruptCtx context.Context) (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 PropertyCheck 

type PropertyCheck func(*ParallelExecutor) error

type ReadDescriptor 

type ReadDescriptor struct {
	Path Key
	Kind int
	V    Version
}

type SafeFIFOQueue 

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

func NewSafeFIFOQueue 

func NewSafeFIFOQueue(capacity int) *SafeFIFOQueue

func (*SafeFIFOQueue) Len 

func (q *SafeFIFOQueue) Len() int

func (*SafeFIFOQueue) Pop 

func (q *SafeFIFOQueue) Pop() interface{}

func (*SafeFIFOQueue) Push 

func (q *SafeFIFOQueue) Push(v int, d interface{})

type SafePriorityQueue 

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

A thread safe priority queue

func NewSafePriorityQueue 

func NewSafePriorityQueue(capacity int) *SafePriorityQueue

func (*SafePriorityQueue) Len 

func (pq *SafePriorityQueue) Len() int

func (*SafePriorityQueue) Pop 

func (pq *SafePriorityQueue) Pop() interface{}

func (*SafePriorityQueue) Push 

func (pq *SafePriorityQueue) Push(v int, d interface{})

type SafeQueue 

type SafeQueue interface {
	Push(v int, d interface{})
	Pop() interface{}
	Len() int
}

type TxBitset 

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

TxBitset is a word-parallel bitset for tracking transaction dependencies. All bitsets operated on together must have the same len(words).

func (*TxBitset) AndNot 

func (b *TxBitset) AndNot(other *TxBitset)

func (*TxBitset) ForEach 

func (b *TxBitset) ForEach(fn func(int))

func (*TxBitset) Or 

func (b *TxBitset) Or(other *TxBitset)

func (*TxBitset) Set 

func (b *TxBitset) Set(i int)

func (*TxBitset) Test 

func (b *TxBitset) Test(i int) bool

func (*TxBitset) ToSlice 

func (b *TxBitset) ToSlice() []int

type TxDep 

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

type TxReadWriteSet 

type TxReadWriteSet struct {
	Index     int
	ReadList  []ReadDescriptor
	WriteList []WriteDescriptor
}

TxReadWriteSet holds a single transaction's read and write sets for dependency tracking.

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

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.