graph.go

     1  // Copyright 2014 Google Inc. All Rights Reserved.
     2  //
     3  // Licensed under the Apache License, Version 2.0 (the "License");
     4  // you may not use this file except in compliance with the License.
     5  // You may obtain a copy of the License at
     6  //
     7  //     http://www.apache.org/licenses/LICENSE-2.0
     8  //
     9  // Unless required by applicable law or agreed to in writing, software
    10  // distributed under the License is distributed on an "AS IS" BASIS,
    11  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    12  // See the License for the specific language governing permissions and
    13  // limitations under the License.
    14  
    15  // Package profile represents a pprof profile as a directed graph.
    16  //
    17  // This package is a simplified fork of github.com/google/pprof/internal/graph.
    18  package profile
    19  
    20  import (
    21  	"fmt"
    22  	"sort"
    23  	"strings"
    24  )
    25  
    26  // Options encodes the options for constructing a graph
    27  type Options struct {
    28  	SampleValue       func(s []int64) int64 // Function to compute the value of a sample
    29  	SampleMeanDivisor func(s []int64) int64 // Function to compute the divisor for mean graphs, or nil
    30  
    31  	DropNegative bool // Drop nodes with overall negative values
    32  
    33  	KeptNodes NodeSet // If non-nil, only use nodes in this set
    34  }
    35  
    36  // Nodes is an ordered collection of graph nodes.
    37  type Nodes []*Node
    38  
    39  // Node is an entry on a profiling report. It represents a unique
    40  // program location.
    41  type Node struct {
    42  	// Info describes the source location associated to this node.
    43  	Info NodeInfo
    44  
    45  	// Function represents the function that this node belongs to. On
    46  	// graphs with sub-function resolution (eg line number or
    47  	// addresses), two nodes in a NodeMap that are part of the same
    48  	// function have the same value of Node.Function. If the Node
    49  	// represents the whole function, it points back to itself.
    50  	Function *Node
    51  
    52  	// Values associated to this node. Flat is exclusive to this node,
    53  	// Cum includes all descendents.
    54  	Flat, FlatDiv, Cum, CumDiv int64
    55  
    56  	// In and out Contains the nodes immediately reaching or reached by
    57  	// this node.
    58  	In, Out EdgeMap
    59  }
    60  
    61  // Graph summarizes a performance profile into a format that is
    62  // suitable for visualization.
    63  type Graph struct {
    64  	Nodes Nodes
    65  }
    66  
    67  // FlatValue returns the exclusive value for this node, computing the
    68  // mean if a divisor is available.
    69  func (n *Node) FlatValue() int64 {
    70  	if n.FlatDiv == 0 {
    71  		return n.Flat
    72  	}
    73  	return n.Flat / n.FlatDiv
    74  }
    75  
    76  // CumValue returns the inclusive value for this node, computing the
    77  // mean if a divisor is available.
    78  func (n *Node) CumValue() int64 {
    79  	if n.CumDiv == 0 {
    80  		return n.Cum
    81  	}
    82  	return n.Cum / n.CumDiv
    83  }
    84  
    85  // AddToEdge increases the weight of an edge between two nodes. If
    86  // there isn't such an edge one is created.
    87  func (n *Node) AddToEdge(to *Node, v int64, residual, inline bool) {
    88  	n.AddToEdgeDiv(to, 0, v, residual, inline)
    89  }
    90  
    91  // AddToEdgeDiv increases the weight of an edge between two nodes. If
    92  // there isn't such an edge one is created.
    93  func (n *Node) AddToEdgeDiv(to *Node, dv, v int64, residual, inline bool) {
    94  	if e := n.Out.FindTo(to); e != nil {
    95  		e.WeightDiv += dv
    96  		e.Weight += v
    97  		if residual {
    98  			e.Residual = true
    99  		}
   100  		if !inline {
   101  			e.Inline = false
   102  		}
   103  		return
   104  	}
   105  
   106  	info := &Edge{Src: n, Dest: to, WeightDiv: dv, Weight: v, Residual: residual, Inline: inline}
   107  	n.Out.Add(info)
   108  	to.In.Add(info)
   109  }
   110  
   111  // NodeInfo contains the attributes for a node.
   112  type NodeInfo struct {
   113  	Name              string
   114  	Address           uint64
   115  	StartLine, Lineno int
   116  }
   117  
   118  // PrintableName calls the Node's Formatter function with a single space separator.
   119  func (i *NodeInfo) PrintableName() string {
   120  	return strings.Join(i.NameComponents(), " ")
   121  }
   122  
   123  // NameComponents returns the components of the printable name to be used for a node.
   124  func (i *NodeInfo) NameComponents() []string {
   125  	var name []string
   126  	if i.Address != 0 {
   127  		name = append(name, fmt.Sprintf("%016x", i.Address))
   128  	}
   129  	if fun := i.Name; fun != "" {
   130  		name = append(name, fun)
   131  	}
   132  
   133  	switch {
   134  	case i.Lineno != 0:
   135  		// User requested line numbers, provide what we have.
   136  		name = append(name, fmt.Sprintf(":%d", i.Lineno))
   137  	case i.Name != "":
   138  		// User requested function name. It was already included.
   139  	default:
   140  		// Do not leave it empty if there is no information at all.
   141  		name = append(name, "<unknown>")
   142  	}
   143  	return name
   144  }
   145  
   146  // NodeMap maps from a node info struct to a node. It is used to merge
   147  // report entries with the same info.
   148  type NodeMap map[NodeInfo]*Node
   149  
   150  // NodeSet is a collection of node info structs.
   151  type NodeSet map[NodeInfo]bool
   152  
   153  // NodePtrSet is a collection of nodes. Trimming a graph or tree requires a set
   154  // of objects which uniquely identify the nodes to keep. In a graph, NodeInfo
   155  // works as a unique identifier; however, in a tree multiple nodes may share
   156  // identical NodeInfos. A *Node does uniquely identify a node so we can use that
   157  // instead. Though a *Node also uniquely identifies a node in a graph,
   158  // currently, during trimming, graphs are rebuilt from scratch using only the
   159  // NodeSet, so there would not be the required context of the initial graph to
   160  // allow for the use of *Node.
   161  type NodePtrSet map[*Node]bool
   162  
   163  // FindOrInsertNode takes the info for a node and either returns a matching node
   164  // from the node map if one exists, or adds one to the map if one does not.
   165  // If kept is non-nil, nodes are only added if they can be located on it.
   166  func (nm NodeMap) FindOrInsertNode(info NodeInfo, kept NodeSet) *Node {
   167  	if kept != nil {
   168  		if _, ok := kept[info]; !ok {
   169  			return nil
   170  		}
   171  	}
   172  
   173  	if n, ok := nm[info]; ok {
   174  		return n
   175  	}
   176  
   177  	n := &Node{
   178  		Info: info,
   179  	}
   180  	nm[info] = n
   181  	if info.Address == 0 && info.Lineno == 0 {
   182  		// This node represents the whole function, so point Function
   183  		// back to itself.
   184  		n.Function = n
   185  		return n
   186  	}
   187  	// Find a node that represents the whole function.
   188  	info.Address = 0
   189  	info.Lineno = 0
   190  	n.Function = nm.FindOrInsertNode(info, nil)
   191  	return n
   192  }
   193  
   194  // EdgeMap is used to represent the incoming/outgoing edges from a node.
   195  type EdgeMap []*Edge
   196  
   197  func (em EdgeMap) FindTo(n *Node) *Edge {
   198  	for _, e := range em {
   199  		if e.Dest == n {
   200  			return e
   201  		}
   202  	}
   203  	return nil
   204  }
   205  
   206  func (em *EdgeMap) Add(e *Edge) {
   207  	*em = append(*em, e)
   208  }
   209  
   210  func (em *EdgeMap) Delete(e *Edge) {
   211  	for i, edge := range *em {
   212  		if edge == e {
   213  			(*em)[i] = (*em)[len(*em)-1]
   214  			*em = (*em)[:len(*em)-1]
   215  			return
   216  		}
   217  	}
   218  }
   219  
   220  // Edge contains any attributes to be represented about edges in a graph.
   221  type Edge struct {
   222  	Src, Dest *Node
   223  	// The summary weight of the edge
   224  	Weight, WeightDiv int64
   225  
   226  	// residual edges connect nodes that were connected through a
   227  	// separate node, which has been removed from the report.
   228  	Residual bool
   229  	// An inline edge represents a call that was inlined into the caller.
   230  	Inline bool
   231  }
   232  
   233  // WeightValue returns the weight value for this edge, normalizing if a
   234  // divisor is available.
   235  func (e *Edge) WeightValue() int64 {
   236  	if e.WeightDiv == 0 {
   237  		return e.Weight
   238  	}
   239  	return e.Weight / e.WeightDiv
   240  }
   241  
   242  // NewGraph computes a graph from a profile.
   243  func NewGraph(prof *Profile, o *Options) *Graph {
   244  	nodes, locationMap := CreateNodes(prof, o)
   245  	seenNode := make(map[*Node]bool)
   246  	seenEdge := make(map[nodePair]bool)
   247  	for _, sample := range prof.Sample {
   248  		var w, dw int64
   249  		w = o.SampleValue(sample.Value)
   250  		if o.SampleMeanDivisor != nil {
   251  			dw = o.SampleMeanDivisor(sample.Value)
   252  		}
   253  		if dw == 0 && w == 0 {
   254  			continue
   255  		}
   256  		for k := range seenNode {
   257  			delete(seenNode, k)
   258  		}
   259  		for k := range seenEdge {
   260  			delete(seenEdge, k)
   261  		}
   262  		var parent *Node
   263  		// A residual edge goes over one or more nodes that were not kept.
   264  		residual := false
   265  
   266  		// Group the sample frames, based on a global map.
   267  		// Count only the last two frames as a call edge. Frames higher up
   268  		// the stack are unlikely to be repeated calls (e.g. runtime.main
   269  		// calling main.main). So adding weights to call edges higher up
   270  		// the stack may be not reflecting the actual call edge weights
   271  		// in the program. Without a branch profile this is just an
   272  		// approximation.
   273  		i := 1
   274  		if last := len(sample.Location) - 1; last < i {
   275  			i = last
   276  		}
   277  		for ; i >= 0; i-- {
   278  			l := sample.Location[i]
   279  			locNodes := locationMap.get(l.ID)
   280  			for ni := len(locNodes) - 1; ni >= 0; ni-- {
   281  				n := locNodes[ni]
   282  				if n == nil {
   283  					residual = true
   284  					continue
   285  				}
   286  				// Add cum weight to all nodes in stack, avoiding double counting.
   287  				_, sawNode := seenNode[n]
   288  				if !sawNode {
   289  					seenNode[n] = true
   290  					n.addSample(dw, w, false)
   291  				}
   292  				// Update edge weights for all edges in stack, avoiding double counting.
   293  				if (!sawNode || !seenEdge[nodePair{n, parent}]) && parent != nil && n != parent {
   294  					seenEdge[nodePair{n, parent}] = true
   295  					parent.AddToEdgeDiv(n, dw, w, residual, ni != len(locNodes)-1)
   296  				}
   297  
   298  				parent = n
   299  				residual = false
   300  			}
   301  		}
   302  		if parent != nil && !residual {
   303  			// Add flat weight to leaf node.
   304  			parent.addSample(dw, w, true)
   305  		}
   306  	}
   307  
   308  	return selectNodesForGraph(nodes, o.DropNegative)
   309  }
   310  
   311  func selectNodesForGraph(nodes Nodes, dropNegative bool) *Graph {
   312  	// Collect nodes into a graph.
   313  	gNodes := make(Nodes, 0, len(nodes))
   314  	for _, n := range nodes {
   315  		if n == nil {
   316  			continue
   317  		}
   318  		if n.Cum == 0 && n.Flat == 0 {
   319  			continue
   320  		}
   321  		if dropNegative && isNegative(n) {
   322  			continue
   323  		}
   324  		gNodes = append(gNodes, n)
   325  	}
   326  	return &Graph{gNodes}
   327  }
   328  
   329  type nodePair struct {
   330  	src, dest *Node
   331  }
   332  
   333  // isNegative returns true if the node is considered as "negative" for the
   334  // purposes of drop_negative.
   335  func isNegative(n *Node) bool {
   336  	switch {
   337  	case n.Flat < 0:
   338  		return true
   339  	case n.Flat == 0 && n.Cum < 0:
   340  		return true
   341  	default:
   342  		return false
   343  	}
   344  }
   345  
   346  type locationMap struct {
   347  	s []Nodes          // a slice for small sequential IDs
   348  	m map[uint64]Nodes // fallback for large IDs (unlikely)
   349  }
   350  
   351  func (l *locationMap) add(id uint64, n Nodes) {
   352  	if id < uint64(len(l.s)) {
   353  		l.s[id] = n
   354  	} else {
   355  		l.m[id] = n
   356  	}
   357  }
   358  
   359  func (l locationMap) get(id uint64) Nodes {
   360  	if id < uint64(len(l.s)) {
   361  		return l.s[id]
   362  	} else {
   363  		return l.m[id]
   364  	}
   365  }
   366  
   367  // CreateNodes creates graph nodes for all locations in a profile. It
   368  // returns set of all nodes, plus a mapping of each location to the
   369  // set of corresponding nodes (one per location.Line).
   370  func CreateNodes(prof *Profile, o *Options) (Nodes, locationMap) {
   371  	locations := locationMap{make([]Nodes, len(prof.Location)+1), make(map[uint64]Nodes)}
   372  	nm := make(NodeMap, len(prof.Location))
   373  	for _, l := range prof.Location {
   374  		lines := l.Line
   375  		if len(lines) == 0 {
   376  			lines = []Line{{}} // Create empty line to include location info.
   377  		}
   378  		nodes := make(Nodes, len(lines))
   379  		for ln := range lines {
   380  			nodes[ln] = nm.findOrInsertLine(l, lines[ln], o)
   381  		}
   382  		locations.add(l.ID, nodes)
   383  	}
   384  	return nm.nodes(), locations
   385  }
   386  
   387  func (nm NodeMap) nodes() Nodes {
   388  	nodes := make(Nodes, 0, len(nm))
   389  	for _, n := range nm {
   390  		nodes = append(nodes, n)
   391  	}
   392  	return nodes
   393  }
   394  
   395  func (nm NodeMap) findOrInsertLine(l *Location, li Line, o *Options) *Node {
   396  	var objfile string
   397  	if m := l.Mapping; m != nil && m.File != "" {
   398  		objfile = m.File
   399  	}
   400  
   401  	if ni := nodeInfo(l, li, objfile, o); ni != nil {
   402  		return nm.FindOrInsertNode(*ni, o.KeptNodes)
   403  	}
   404  	return nil
   405  }
   406  
   407  func nodeInfo(l *Location, line Line, objfile string, o *Options) *NodeInfo {
   408  	if line.Function == nil {
   409  		return &NodeInfo{Address: l.Address}
   410  	}
   411  	ni := &NodeInfo{
   412  		Address: l.Address,
   413  		Lineno:  int(line.Line),
   414  		Name:    line.Function.Name,
   415  	}
   416  	ni.StartLine = int(line.Function.StartLine)
   417  	return ni
   418  }
   419  
   420  // Sum adds the flat and cum values of a set of nodes.
   421  func (ns Nodes) Sum() (flat int64, cum int64) {
   422  	for _, n := range ns {
   423  		flat += n.Flat
   424  		cum += n.Cum
   425  	}
   426  	return
   427  }
   428  
   429  func (n *Node) addSample(dw, w int64, flat bool) {
   430  	// Update sample value
   431  	if flat {
   432  		n.FlatDiv += dw
   433  		n.Flat += w
   434  	} else {
   435  		n.CumDiv += dw
   436  		n.Cum += w
   437  	}
   438  }
   439  
   440  // String returns a text representation of a graph, for debugging purposes.
   441  func (g *Graph) String() string {
   442  	var s []string
   443  
   444  	nodeIndex := make(map[*Node]int, len(g.Nodes))
   445  
   446  	for i, n := range g.Nodes {
   447  		nodeIndex[n] = i + 1
   448  	}
   449  
   450  	for i, n := range g.Nodes {
   451  		name := n.Info.PrintableName()
   452  		var in, out []int
   453  
   454  		for _, from := range n.In {
   455  			in = append(in, nodeIndex[from.Src])
   456  		}
   457  		for _, to := range n.Out {
   458  			out = append(out, nodeIndex[to.Dest])
   459  		}
   460  		s = append(s, fmt.Sprintf("%d: %s[flat=%d cum=%d] %x -> %v ", i+1, name, n.Flat, n.Cum, in, out))
   461  	}
   462  	return strings.Join(s, "\n")
   463  }
   464  
   465  // Sort returns a slice of the edges in the map, in a consistent
   466  // order. The sort order is first based on the edge weight
   467  // (higher-to-lower) and then by the node names to avoid flakiness.
   468  func (em EdgeMap) Sort() []*Edge {
   469  	el := make(edgeList, 0, len(em))
   470  	for _, w := range em {
   471  		el = append(el, w)
   472  	}
   473  
   474  	sort.Sort(el)
   475  	return el
   476  }
   477  
   478  // Sum returns the total weight for a set of nodes.
   479  func (em EdgeMap) Sum() int64 {
   480  	var ret int64
   481  	for _, edge := range em {
   482  		ret += edge.Weight
   483  	}
   484  	return ret
   485  }
   486  
   487  type edgeList []*Edge
   488  
   489  func (el edgeList) Len() int {
   490  	return len(el)
   491  }
   492  
   493  func (el edgeList) Less(i, j int) bool {
   494  	if el[i].Weight != el[j].Weight {
   495  		return abs64(el[i].Weight) > abs64(el[j].Weight)
   496  	}
   497  
   498  	from1 := el[i].Src.Info.PrintableName()
   499  	from2 := el[j].Src.Info.PrintableName()
   500  	if from1 != from2 {
   501  		return from1 < from2
   502  	}
   503  
   504  	to1 := el[i].Dest.Info.PrintableName()
   505  	to2 := el[j].Dest.Info.PrintableName()
   506  
   507  	return to1 < to2
   508  }
   509  
   510  func (el edgeList) Swap(i, j int) {
   511  	el[i], el[j] = el[j], el[i]
   512  }
   513  
   514  func abs64(i int64) int64 {
   515  	if i < 0 {
   516  		return -i
   517  	}
   518  	return i
   519  }
   520
View as plain text