dependencygraph2

package
v3.3.0+incompatible Latest Latest
Warning

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

 Go to latest Published: Jan 13, 2023 License: Apache-2.0 Imports: 17 Imported by: 0

README

Dependency graph

The dependency graph tracks dependencies between the commands of a capture.

This doc is an overview of the dependency graph internals. As the code evolves, the few code snippets used here may not match the latest version, but should still help to understand the high-level approach.

In general, Command B depends on command A if command A has some side-effect to the API state or some resource (image, buffer...) memory that impacts command B.

To take a small Vulkan example:

vkCmdSetScissor(...);  // Update the scissor value in Vulkan state
vkCmdDraw(...);        // Draw is affected by the scissor value

Here, vkCmdSetScissor() updates the scissor value of the associated graphics pipeline in the Vulkan API state, then vkCmdDraw() performs a draw that is impacted by this scissor value. Hence, vkCmdDraw() depends on vkCmdSetScissor().

The dependency graph establishes dependencies between the commands of a trace by tracking each command's accesses to memory and the API state. It was introduced to help with dead-code elimination (i.e. removing irrelevant commands from a capture for a given replay), but it might be relevant to other use-cases.

A dependency graph example

The dependency graph is meant to be used internally and not directly presented to the end user. Still, in order to understand it, it is good to see what it looks like some simple examples.

You can view the dependency graph of a given capture using the create_graph_visualization gapit verb, e.g.:

./gapit create_graph_visualization -format dot -out depgraph.dot com.example.gfxtrace

Warning: the dependency graph gets quickly fairly big on traces of real games, you might not be able to easily explore them using a DOT viewer.

The dependency graph of a trace of one frame of Sascha Willems triangle demo looks like this (as of October 2020):

Dependency graph of a simple Vulkan triangle demo

We can see that vkQueuePresent has a dependency edge pointing to vkCmdEndRenderPass, which reflects the fact that the render pass must be executed before the frame is presented. Now, vkCmdEndRenderPass itself transitively depends on all commands of the command buffer that was submitted, eventually leading to vkQueueSubmit. Also, vkCmdDrawIndexed depends on the several commands that performs all the required setup (vkCmdBindPipeline, vkCmdBindIndexBuffer, etc), but these setup commands do not depend on each other, as they can be performed in any order.

Structure of the dependency graph

The DependencyGraph interface defines possible operations on a dependency graph, and it is implemented by the dependencyGraph type.

The graph nodes are defined by the Node interface, which is implemented by two kinds of nodes: CmdNode represents an API command or subcommand, and ObsNode represents a memory observation. The graph also stores dependencies between the nodes: these dependencies are untyped, they are just represented by an ordered pair of node IDs, such that there is a source node and a target node.

For all nodes, the graph stores the node accesses to API state and memory in a NodeAccesses type, which is retrievable via GetNodeAccesses(). Note that these accesses are saved only if the SaveNodeAccesses field of the DependencyGraphConfig object used at graph creation time is set to true. There are several kinds of node accesses, the main two are FragmentAccess which represent an access to a part (a "fragment") of the API state, and MemoryAccess which represents an access to some memory.

Creation of the dependency graph

The dependency graph is created by mutating all the capture commands and monitoring their accesses to API state and memory.

Approach overview

Let's give a high-level, conceptual illustration of this process: consider we have a memory made of two slots, each slot being an addressable part of the memory. When building the dependency graph, for each slot we remember the ID of the node that was the latest to write to this memory. Say during mutation we are at a point where the latest node to write to slot 1 was node 11, and the latest to write to slot 2 was 22:

slot1: 11
slot2: 22

Now, we mutate the next command whose CmdNode ID is 33. This command reads from slot1, and read-writes to slot2. Since it reads from both slots, it depends on both node 11 and 22. As it writes to slot2, at the end of the command mutation, the memory accesses tracker is updated to:

slot1: 11
slot2: 33

This makes sure that the next command to read from slot2 will depend on 33.

Now, a single command may have multiple read/write to the same slot: we should not update the memory access tracker as soon as there is a write, otherwise a subsequent read by the same command would create a circular dependency to the node itself. To avoid this, all read/writes of a single command are temporarily stored in a list of pending accesses, which are flushed (see the various Flush() functions) when the command ends.

In practice

In practice, in BuildDependencyGraph(), a dependencyGraphBuilder is created and passed as the api.StateWatcher to each command's Mutate(). The api.StateWatcher interface lists callbacks that are invoked during mutation, including when a command or subcommand starts or ends, and whenever it does an API state access (OnReadFrag()/OnWriteFrag()) or a memory access (OnReadSlice()/OnWriteSlice() and OnReadObs()/OnWriteObs()).

The dependencyGraphBuilder builder object contains itself some dedicated sub-watchers like a FragWatcher and a MemWatcher, which focus on API state and memory, respectively. These watcher accumulate pending accesses of a command and its potential subcommands (so there can be several nodes pending), and dependencies are established when a top-level command ends: OnEndCmd() calls AddDependencies() that calls AddNodeDependencies() on each pending node.

The tracking of API state fragment and memory accesses is done in an API-agnostic way, there is no direct correlation with e.g. Vulkan state or objects. This tracking is also more complex than the simplified memory slots used to illustrate the approach. Basically, a memory access is defined by an interval.U64Span within a given memory.PoolID, and an API state fragment access is defined by some api.RefID and api.Fragment. In both cases, the high-level approach presented above applies.

Forward dependencies

Forward dependencies are a special kind of dependency that applies to API commands that come in pairs. For instance, vkBeginCommandBuffer() and vkEndCommandBuffer() come in pairs: if you have one, you should have the other.

In practice, alongside the FragWatcher and the MemWatcher, the dependency graph buidler also has a ForwardWatcher which handles forward dependencies via three callbacks: OpenForwardDependency(), CloseForwardDependency() and DropForwardDependency().

Most forward dependencies are only concerned with open and close operations. For instance, the mutation of vkBeginCommandBuffer() triggers OpenForwardDependency() that creates an open forward dependency, and vkEndCommandBuffer() triggers CloseForwardDependency() that closes it, marking the dependency between these two commands. Open and close are matched on a dependencyID that, as empty interface, could be anything. In the case of vkBegin/EndCommandBuffer, the command buffer Vulkan handle is used as a dependencyID. Other kinds of command pairs are the vkCreate*() and vkDestroy*() ones.

DropForwardDependency() is handy for Vulkan fences: the signal and wait operations of a fence usually come in pairs, but a vkResetFences() can also unsignal fences. In this case, mutation of vkResetFences() triggers a DropForwardDependency() on all relevant fences, to mark that the fence resetting disallows a signal/wait dependency, without depending itself on previous signal operations.

Documentation

Index

Constants

View Source 
const NodeNoID = NodeID(math.MaxUint32)

Variables

This section is empty.

Functions

func DCECapture 

func DCECapture(ctx context.Context, name string, p *path.Capture, requestedCmds []*path.Command) (*path.Capture, error)

DCECapture returns a new capture containing only the requested commands and their dependencies.

func NewForwardWatcher 

func NewForwardWatcher() *forwardWatcher

func NewFragWatcher 

func NewFragWatcher() *fragWatcher

func NewGraphBuilder 

func NewGraphBuilder(ctx context.Context, config DependencyGraphConfig,
	c *capture.GraphicsCapture, initialCmds []api.Cmd, state *api.GlobalState) *graphBuilder

func NewMemWatcher 

func NewMemWatcher() *memWatcher

Types

type AccessMode 

type AccessMode uint

AccessMode is a bitfield that records read/write accesses 

const (

	// PLAIN: just plain read/write accesses
	ACCESS_PLAIN_READ AccessMode = 1 << iota
	ACCESS_PLAIN_WRITE
	// DEP: read/write relevant for dependencies
	ACCESS_DEP_READ
	ACCESS_DEP_WRITE
	// Combined values
	ACCESS_READ  AccessMode = ACCESS_DEP_READ | ACCESS_PLAIN_READ
	ACCESS_WRITE AccessMode = ACCESS_DEP_WRITE | ACCESS_PLAIN_WRITE
)

type Accesses 

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

type CmdContext 

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

type CmdNode 

type CmdNode struct {
	Index    api.SubCmdIdx
	CmdFlags api.CmdFlags
}

CmdNode is a dependency node corresponding to an API call

type DCEBuilder 

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

DCEBuilder tracks the data necessary to perform dead-command-eliminition on a capture

func NewDCEBuilder 

func NewDCEBuilder(graph DependencyGraph) *DCEBuilder

NewDCEBuilder creates a new DCEBuiler using the specified dependency graph

func (*DCEBuilder) BuffersCommands 

func (t *DCEBuilder) BuffersCommands() bool

func (*DCEBuilder) Build 

func (b *DCEBuilder) Build(ctx context.Context) error

Build runs the dead-code-elimination. The subcommands specified in cmds are marked alive, along with their transitive dependencies.

func (*DCEBuilder) Flush 

func (b *DCEBuilder) Flush(ctx context.Context, out transform.Writer) error

Flush is to comform the interface of Transformer. Flush performs DCE, and sends the live commands to the writer

func (*DCEBuilder) LiveCmdID 

func (b *DCEBuilder) LiveCmdID(oldCmdID api.CmdID) api.CmdID

LiveCmdID maps CmdIDs from the original capture to CmdIDs in within the live commands. If the old CmdID refers to a dead command, the returned command will refer to the next live command; if there is no next live command, api.CmdNoID is returned.

func (*DCEBuilder) LiveCmds 

func (b *DCEBuilder) LiveCmds() []api.Cmd

LiveCmds returns the live commands

func (*DCEBuilder) LogStats 

func (b *DCEBuilder) LogStats(ctx context.Context)

func (*DCEBuilder) NumLiveInitCmds 

func (b *DCEBuilder) NumLiveInitCmds() int

NumLiveInitiCmds returns the number of live commands which are initial commands. (Initial commands are generated commands to recreate the initial state).

func (*DCEBuilder) OriginalCmdID 

func (b *DCEBuilder) OriginalCmdID(liveCmdID api.CmdID) api.CmdID

OriginalCmdIDs maps a live CmdID to the CmdID of the corresponding command in the original capture

func (*DCEBuilder) PostLoop 

func (b *DCEBuilder) PostLoop(ctx context.Context, out transform.Writer)

func (*DCEBuilder) PreLoop 

func (b *DCEBuilder) PreLoop(ctx context.Context, out transform.Writer)

func (*DCEBuilder) Request 

func (b *DCEBuilder) Request(ctx context.Context, fci api.SubCmdIdx) error

Request added a requsted command or subcommand, represented by its full command index, to the DCE.

func (*DCEBuilder) Transform 

func (*DCEBuilder) Transform(ctx context.Context, id api.CmdID, c api.Cmd, out transform.Writer) error

Transform is to comform the interface of Transformer, but does not accept any input.

type DependencyGraph 

type DependencyGraph interface {

	// NumNodes returns the number of nodes in the graph
	NumNodes() int

	// NumDependencies returns the number of dependencies (edges) in the graph
	NumDependencies() uint64

	// GetNode returns the node data associated with the given NodeID
	GetNode(NodeID) Node

	// GetNodeID returns the NodeID associated with given node data
	GetCmdNodeID(api.CmdID, api.SubCmdIdx) NodeID

	// GetCmdAncestorNodeIDs returns the NodeIDs associated with the ancestors of the
	// given subcommand.
	GetCmdAncestorNodeIDs(api.CmdID, api.SubCmdIdx) []NodeID

	// ForeachCmd iterates over all API calls in the graph.
	// If IncludeInitialCommands is true, this includes the initial commands
	// which reconstruct the initial state.
	// CmdIDs for initial commands are:
	//   CmdID(0).Derived(), CmdID(1).Derived(), ...
	// Whether or not IncludeInitialCommands is true, the CmdIDs for captured
	// commands are: 0, 1, 2, ...
	ForeachCmd(ctx context.Context,
		cb func(context.Context, api.CmdID, api.Cmd) error) error

	// ForeachNode iterates over all nodes in the graph in chronological order.
	// I.e., the following order:
	//   * For each initial command
	//     * Read observation nodes for this command
	//     * command node
	//     * Write observation nodes for this command
	//   * For each (non-initial) command
	//     * Read observation nodes for this command
	//     * command node
	//     * Write observation nodes for this command
	ForeachNode(cb func(NodeID, Node) error) error

	// ForeachDependency iterates over all pairs (src, tgt), where src depends on tgt
	ForeachDependency(cb func(NodeID, NodeID) error) error

	// ForeachDependencyFrom iterates over all the nodes tgt, where src depends on tgt
	ForeachDependencyFrom(src NodeID, cb func(NodeID) error) error

	// ForeachDependencyTo iterates over all the nodes src, where src depends on tgt.
	// If Config().ReverseDependencies is false, this will return an error.
	ForeachDependencyTo(tgt NodeID, cb func(NodeID) error) error

	// Capture returns the capture whose dependencies are stored in this graph
	Capture() *capture.GraphicsCapture

	// GetUnopenedForwardDependencies returns the commands that have dependencies that
	// are not part of the capture.
	GetUnopenedForwardDependencies() []api.CmdID

	// GetCommand returns the command identified by the given CmdID
	GetCommand(api.CmdID) api.Cmd

	// NumInitialCommands returns the number of initial commands
	// (the commands needed to reconstruct the initial state before the
	// first command in the capture)
	NumInitialCommands() int

	GetNodeAccesses(NodeID) NodeAccesses

	// Config returns the config used to create this graph
	Config() DependencyGraphConfig
}

DependencyGraph stores the dependencies among api calls and memory observations,

func BuildDependencyGraph 

func BuildDependencyGraph(ctx context.Context, config DependencyGraphConfig,
	c *capture.GraphicsCapture, initialCmds []api.Cmd, initialRanges interval.U64RangeList) (DependencyGraph, error)

func GetDependencyGraph 

func GetDependencyGraph(ctx context.Context, c *path.Capture, config DependencyGraphConfig) (DependencyGraph, error)

func TryGetDependencyGraph 

func TryGetDependencyGraph(ctx context.Context, c *path.Capture, config DependencyGraphConfig) (DependencyGraph, error)

type DependencyGraphConfig 

type DependencyGraphConfig struct {
	// MergeSubCmdNodes indicates whether the graph should have one node per
	// command (true), or a separate node for each subcommand (false)
	MergeSubCmdNodes bool

	// IncludeInitialCommands indicates whether nodes should be created for
	// the initial (state rebuild) commands
	IncludeInitialCommands bool

	// ReverseDependencies indicates whether reverse edges should be created
	ReverseDependencies bool

	SaveNodeAccesses bool
}

Information about what sort of data to store in a dependency graph

type Distribution 

type Distribution struct {
	SmallBins []uint64
	LargeBins map[uint64]uint64
}

func (Distribution) Add 

func (d Distribution) Add(x uint64)

type ForwardAccess 

type ForwardAccess struct {
	Nodes        *ForwardNodes
	DependencyID interface{}
	Mode         ForwardAccessMode
}

type ForwardAccessMode 

type ForwardAccessMode uint
const (
	FORWARD_OPEN ForwardAccessMode = iota + 1
	FORWARD_CLOSE
	FORWARD_DROP
)

type ForwardNodes 

type ForwardNodes struct {
	Open  NodeID
	Close NodeID
	Drop  NodeID
}

type ForwardWatcher 

type ForwardWatcher interface {
	OpenForwardDependency(ctx context.Context, cmdCtx CmdContext, dependencyID interface{})
	CloseForwardDependency(ctx context.Context, cmdCtx CmdContext, dependencyID interface{})
	DropForwardDependency(ctx context.Context, cmdCtx CmdContext, dependencyID interface{})
	OnBeginCmd(ctx context.Context, cmdCtx CmdContext)
	OnEndCmd(ctx context.Context, cmdCtx CmdContext) Accesses
	OnBeginSubCmd(ctx context.Context, cmdCtx CmdContext, subCmdCtx CmdContext)
	OnEndSubCmd(ctx context.Context, cmdCtx CmdContext)
}

type FragWatcher 

type FragWatcher interface {
	OnReadFrag(ctx context.Context, cmdCtx CmdContext, owner api.RefObject, f api.Fragment, v api.RefObject, track bool)
	OnWriteFrag(ctx context.Context, cmdCtx CmdContext, owner api.RefObject, f api.Fragment, old api.RefObject, new api.RefObject, track bool)
	OnBeginCmd(ctx context.Context, cmdCtx CmdContext)
	OnEndCmd(ctx context.Context, cmdCtx CmdContext) map[NodeID][]FragmentAccess
	OnBeginSubCmd(ctx context.Context, cmdCtx CmdContext, subCmdCtx CmdContext)
	OnEndSubCmd(ctx context.Context, cmdCtx CmdContext)
	GetStateRefs() map[api.RefID]RefFrag
}

type FragmentAccess 

type FragmentAccess struct {
	Node     NodeID
	Ref      api.RefID
	Fragment api.Fragment
	Mode     AccessMode
	Deps     []NodeID
}

type GraphBuilder 

type GraphBuilder interface {
	AddDependencies(context.Context,
		map[NodeID][]FragmentAccess,
		map[NodeID][]MemoryAccess,
		map[NodeID][]ForwardAccess,
		bool)
	BuildReverseDependencies()
	GetCmdNodeID(api.CmdID, api.SubCmdIdx) NodeID
	GetOrCreateCmdNodeID(context.Context, api.CmdID, api.SubCmdIdx, api.Cmd) NodeID
	GetObsNodeIDs(api.CmdID, []api.CmdObservation, bool) []NodeID
	GetCmdContext(context.Context, api.CmdID, api.Cmd) CmdContext
	GetSubCmdContext(api.CmdID, api.SubCmdIdx) CmdContext
	GetNodeStats(NodeID) *NodeStats
	GetStats() *GraphBuilderStats
	GetGraph() *dependencyGraph
	OnBeginCmd(ctx context.Context, cmdCtx CmdContext)
	OnBeginSubCmd(ctx context.Context, cmdCtx CmdContext, subCmdCtx CmdContext, recordIdx api.RecordIdx)
	OnRecordSubCmd(ctx context.Context, cmdCtx CmdContext, recordIdx api.RecordIdx)
}

type GraphBuilderStats 

type GraphBuilderStats struct {
	UniqueFragReads     uint64
	UniqueFragWrites    uint64
	UniqueMemReads      uint64
	UniqueMemWrites     uint64
	UniqueDeps          uint64
	NumDeps             uint64
	NumFragDeps         uint64
	NumCompleteFragDeps uint64
	NumMemDeps          uint64
	NumCmdNodes         uint64
	NumObsNodes         uint64
	DepDist             Distribution
}

type MemWatcher 

type MemWatcher interface {
	OnWriteSlice(ctx context.Context, cmdCtx CmdContext, s memory.Slice)
	OnReadSlice(ctx context.Context, cmdCtx CmdContext, s memory.Slice)
	OnWriteObs(ctx context.Context, cmdCtx CmdContext, obs []api.CmdObservation, nodes []NodeID)
	OnReadObs(ctx context.Context, cmdCtx CmdContext, obs []api.CmdObservation, nodes []NodeID)
	OnBeginCmd(ctx context.Context, cmdCtx CmdContext)
	OnEndCmd(ctx context.Context, cmdCtx CmdContext) map[NodeID][]MemoryAccess
	OnBeginSubCmd(ctx context.Context, cmdCtx CmdContext, subCmdCtx CmdContext)
	OnEndSubCmd(ctx context.Context, cmdCtx CmdContext)
}

type MemoryAccess 

type MemoryAccess struct {
	Node NodeID
	Pool memory.PoolID
	Span interval.U64Span
	Mode AccessMode
	Deps []NodeID
}

type Node 

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

Node represents a node in the dependency graph, and holds data about the associated command or memory observation.

type NodeAccesses 

type NodeAccesses struct {
	FragmentAccesses []FragmentAccess
	MemoryAccesses   []MemoryAccess
	ForwardAccesses  []ForwardAccess
	ParentNode       NodeID
	InitCmdNodes     []NodeID
}

type NodeID 

type NodeID uint32

NodeID identifies a node in a dependency graph

type NodeIDSorter 

type NodeIDSorter struct {
	Nodes []NodeID
}

NodeIDSorter is a structure to use for sorting NodeIDs in the sort package

func (*NodeIDSorter) Len 

func (s *NodeIDSorter) Len() int

Len returns the length of the node list

func (*NodeIDSorter) Less 

func (s *NodeIDSorter) Less(i, j int) bool

Less returns trus if the elements at index i are less than j

func (*NodeIDSorter) Swap 

func (s *NodeIDSorter) Swap(i, j int)

Swap swaps the locations of 2 nodes in the list

type NodeStats 

type NodeStats struct {
	NumFragReads        uint64
	NumFragWrites       uint64
	NumMemReads         uint64
	NumMemWrites        uint64
	NumForwardDepOpens  uint64
	NumForwardDepCloses uint64
	NumForwardDepDrops  uint64
	NumDeps             uint64
	NumFragDeps         uint64
	NumCompleteFragDeps uint64
	NumMemDeps          uint64
	UniqueFragReads     uint64
	UniqueFragWrites    uint64
	UniqueMemReads      uint64
	UniqueMemWrites     uint64
	UniqueDeps          uint64
}

type ObsNode 

type ObsNode struct {
	CmdObservation api.CmdObservation
	CmdID          api.CmdID
	IsWrite        bool
	Index          int
}

ObsNode is a dependency node corresponding to a memory observation

type RecordNodeTrie 

type RecordNodeTrie struct {
	api.SubCmdIdxTrie
}

func (*RecordNodeTrie) GetRecordNode 

func (t *RecordNodeTrie) GetRecordNode(recordIdx api.RecordIdx) NodeID

func (*RecordNodeTrie) SetRecordNode 

func (t *RecordNodeTrie) SetRecordNode(recordIdx api.RecordIdx, nodeID NodeID)

type RefFrag 

type RefFrag struct {
	RefID api.RefID
	Frag  api.Fragment
}

Source Files

View all Source files

Directories

Path Synopsis

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.