sync

Documentation

Overview

Package sync provides interfaces for managing externally synchronized APIs.

The methods allow queries to be performed on an API to allow the determination of where blocking operations between threads of execution happen. These methods allow us to reason about execution in a non-linear way.

Index

• func MutateWithSubcommands(ctx context.Context, c *path.Capture, cmds []api.Cmd, ...) error
• func MutationCmdsFor(ctx context.Context, c *path.Capture, data *Data, cmds []api.Cmd, id api.CmdID, ...) ([]api.Cmd, error)
• type AbstractNode
• type CmdNode
• type Data
  • func NewData() *Data
• type ExecutionRanges
  • func (e ExecutionRanges) SortedKeys() SynchronizationIndices
• type NoMECSubcommandsError
  • func (e NoMECSubcommandsError) Error() string
• type SubcommandReference
• type SyncNode
• type SyncNodeIdx
• type SynchronizationIndices
  • func (s SynchronizationIndices) Len() int
  • func (s SynchronizationIndices) Less(i, j int) bool
  • func (s SynchronizationIndices) Swap(i, j int)
• type SynchronizedAPI

Functions

func MutateWithSubcommands

func MutateWithSubcommands(ctx context.Context, c *path.Capture, cmds []api.Cmd,
	postCmdCb func(*api.GlobalState, api.SubCmdIdx, api.Cmd),
	preSubCmdCb func(*api.GlobalState, api.SubCmdIdx, api.Cmd),
	postSubCmdCb func(*api.GlobalState, api.SubCmdIdx, api.Cmd)) error

MutateWithSubcommands mutates a list of commands. And after mutating each Cmd, the given post-Cmd callback will be called. And the given pre-subcommand callback and the post-subcommand callback will be called before and after calling each subcommand callback function.

func MutationCmdsFor

func MutationCmdsFor(ctx context.Context, c *path.Capture, data *Data, cmds []api.Cmd, id api.CmdID, subindex api.SubCmdIdx, initialCall bool) ([]api.Cmd, error)

MutationCmdsFor returns a list of command that represent the correct mutations to have the state for all commands before and including the given index.

Types

type AbstractNode

type AbstractNode struct{}

AbstractNode is a node in the sync dependency graph that doesn't correspond to any point in the trace and is just used as a marker.

type CmdNode

type CmdNode struct {
	Idx api.SubCmdIdx
}

CmdNode is a node in the sync dependency graph that is a command.

type Data

type Data struct {
	// SubcommandReferences contains the information about every subcommand
	// run by a particular command.
	SubcommandReferences map[api.CmdID][]SubcommandReference
	// SubcommandGroups represents the last Subcommand in every command buffer.
	SubcommandGroups map[api.CmdID][]api.SubCmdIdx
	// Hidden contains all the commands that should be hidden from the regular
	// command tree as they exist as a subcommand of another command.
	Hidden api.CmdIDSet
	// SubCommandMarkerGroups contains all the marker groups in the subcommands,
	// indexed by the immediate parent of the subcommands in the group.
	// e.g.: group: [73, 1, 4, 5~6] should be indexed by [73, 1, 4]
	SubCommandMarkerGroups *subCommandMarkerGroupTrie
	// SyncDependencies contains the commands that must complete
	// (according to their fences or semaphores) before they can be executed.
	SyncDependencies map[SyncNodeIdx][]SyncNodeIdx
	SyncNodes        []SyncNode
	CmdSyncNodes     map[api.CmdID]SyncNodeIdx
	SubcommandLookup *api.SubCmdIdxTrie
	// UnblockingCommands is a map of what command fully unblocks
	// some other command. Or to put it another way, the command that answers
	// the question: If we want to play up to command N, what command do we
	// have to replay until, in order to prevent a deadlock.
	UnblockingCommands map[api.CmdID]api.CmdID
}

Data contains a map of synchronization pairs.

func NewData

func NewData() *Data

NewData creates a new clean Data object

type ExecutionRanges

type ExecutionRanges struct {
	// LastIndex is the final subcommand that exists within this command.
	LastIndex api.SubCmdIdx
	// Ranges defines which future command will unblock the command in question, and
	// which subcommand is the last that will be run at that point.
	Ranges map[api.CmdID]api.SubCmdIdx
}

ExecutionRanges contains the information about a blocked command.

func (ExecutionRanges) SortedKeys

func (e ExecutionRanges) SortedKeys() SynchronizationIndices

SortedKeys returns the keys of 'e' in sorted order

type NoMECSubcommandsError

type NoMECSubcommandsError struct{}

NoMECSubcommandsError is used to notify the caller that this API does not support MEC subcommands.

func (NoMECSubcommandsError) Error

func (e NoMECSubcommandsError) Error() string

type SubcommandReference

type SubcommandReference struct {
	Index api.SubCmdIdx
	// If api.CmdID is api.CmdNoID then the generating command came from before
	// the start of the trace.
	GeneratingCmd api.CmdID
	// If GeneratingCmd is nil, then MidExecutionCommandData contains the data
	// that the API needs in order to reconstruct this command.
	MidExecutionCommandData interface{}
	// IsCalledGroup is true if the reference is to a nested call, otherwise
	// the reference belongs to a command-list.
	IsCallerGroup bool
}

SubcommandReference contains a subcommand index as well as an api.CmdID that references the command that generated this subcommand.

type SyncNode

type SyncNode interface {
	// contains filtered or unexported methods
}

SyncNode is the interface implemented by types that can be used as vertices in the sync dependency graph.

type SyncNodeIdx

type SyncNodeIdx uint64

SyncNodeIdx is the identifier for a node in the sync dependency graph.

type SynchronizationIndices

type SynchronizationIndices []api.CmdID

SynchronizationIndices is a list of command identifiers, defining the location of a one side synchronization dependency.

func (SynchronizationIndices) Len

func (s SynchronizationIndices) Len() int

Len returns the length of subcommand indices

func (SynchronizationIndices) Less

func (s SynchronizationIndices) Less(i, j int) bool

Less returns true if s[i] < s[j]

func (SynchronizationIndices) Swap

func (s SynchronizationIndices) Swap(i, j int)

Swap swaps the 2 subcommands in the given slice

type SynchronizedAPI

type SynchronizedAPI interface {
	// GetTerminator returns a transform that will allow the given capture to be terminated
	// after a command.
	GetTerminator(ctx context.Context, c *path.Capture) (transform.Terminator, error)

	// ResolveSynchronization resolve all of the synchronization information for
	// the given API.
	ResolveSynchronization(ctx context.Context, d *Data, c *path.Capture) error

	// MutateSubcommands mutates the given Cmd and calls callbacks for subcommands
	// attached to that Cmd. preSubCmdCallback and postSubCmdCallback will be
	// called before and after executing each subcommand callback.
	MutateSubcommands(ctx context.Context, id api.CmdID, cmd api.Cmd, s *api.GlobalState,
		preSubCmdCallback func(*api.GlobalState, api.SubCmdIdx, api.Cmd),
		postSubCmdCallback func(*api.GlobalState, api.SubCmdIdx, api.Cmd)) error

	// FlattenSubcommandIdx returns the flatten command id for the subcommand
	// specified by the given SubCmdIdx. If flattening succeeded, the flatten
	// command id and true will be returned, otherwise, zero and false will be
	// returned.
	FlattenSubcommandIdx(idx api.SubCmdIdx, d *Data, initialCall bool) (api.CmdID, bool)

	// RecoverMidExecutionCommand returns a virtual command, used to describe the
	// a subcommand that was created before the start of the trace.
	// If the api does not have mid-execution commands, NoMECSubcommandsError should be returned.
	RecoverMidExecutionCommand(ctx context.Context, c *path.Capture, data interface{}) (api.Cmd, error)

	// IsTrivialTerminator returns true if stopping at the given command is trivial.
	IsTrivialTerminator(ctx context.Context, c *path.Capture, cmd api.SubCmdIdx) (bool, error)
}

SynchronizedAPI defines an API that explicitly has multiple threads of execution. This means that replays are not necessarily linear in terms of commands.