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  		clear(seenNode)
   257  		clear(seenEdge)
   258  		var parent *Node
   259  		// A residual edge goes over one or more nodes that were not kept.
   260  		residual := false
   261  
   262  		// Group the sample frames, based on a global map.
   263  		// Count only the last two frames as a call edge. Frames higher up
   264  		// the stack are unlikely to be repeated calls (e.g. runtime.main
   265  		// calling main.main). So adding weights to call edges higher up
   266  		// the stack may be not reflecting the actual call edge weights
   267  		// in the program. Without a branch profile this is just an
   268  		// approximation.
   269  		i := 1
   270  		if last := len(sample.Location) - 1; last < i {
   271  			i = last
   272  		}
   273  		for ; i >= 0; i-- {
   274  			l := sample.Location[i]
   275  			locNodes := locationMap.get(l.ID)
   276  			for ni := len(locNodes) - 1; ni >= 0; ni-- {
   277  				n := locNodes[ni]
   278  				if n == nil {
   279  					residual = true
   280  					continue
   281  				}
   282  				// Add cum weight to all nodes in stack, avoiding double counting.
   283  				_, sawNode := seenNode[n]
   284  				if !sawNode {
   285  					seenNode[n] = true
   286  					n.addSample(dw, w, false)
   287  				}
   288  				// Update edge weights for all edges in stack, avoiding double counting.
   289  				if (!sawNode || !seenEdge[nodePair{n, parent}]) && parent != nil && n != parent {
   290  					seenEdge[nodePair{n, parent}] = true
   291  					parent.AddToEdgeDiv(n, dw, w, residual, ni != len(locNodes)-1)
   292  				}
   293  
   294  				parent = n
   295  				residual = false
   296  			}
   297  		}
   298  		if parent != nil && !residual {
   299  			// Add flat weight to leaf node.
   300  			parent.addSample(dw, w, true)
   301  		}
   302  	}
   303  
   304  	return selectNodesForGraph(nodes, o.DropNegative)
   305  }
   306  
   307  func selectNodesForGraph(nodes Nodes, dropNegative bool) *Graph {
   308  	// Collect nodes into a graph.
   309  	gNodes := make(Nodes, 0, len(nodes))
   310  	for _, n := range nodes {
   311  		if n == nil {
   312  			continue
   313  		}
   314  		if n.Cum == 0 && n.Flat == 0 {
   315  			continue
   316  		}
   317  		if dropNegative && isNegative(n) {
   318  			continue
   319  		}
   320  		gNodes = append(gNodes, n)
   321  	}
   322  	return &Graph{gNodes}
   323  }
   324  
   325  type nodePair struct {
   326  	src, dest *Node
   327  }
   328  
   329  // isNegative returns true if the node is considered as "negative" for the
   330  // purposes of drop_negative.
   331  func isNegative(n *Node) bool {
   332  	switch {
   333  	case n.Flat < 0:
   334  		return true
   335  	case n.Flat == 0 && n.Cum < 0:
   336  		return true
   337  	default:
   338  		return false
   339  	}
   340  }
   341  
   342  type locationMap struct {
   343  	s []Nodes          // a slice for small sequential IDs
   344  	m map[uint64]Nodes // fallback for large IDs (unlikely)
   345  }
   346  
   347  func (l *locationMap) add(id uint64, n Nodes) {
   348  	if id < uint64(len(l.s)) {
   349  		l.s[id] = n
   350  	} else {
   351  		l.m[id] = n
   352  	}
   353  }
   354  
   355  func (l locationMap) get(id uint64) Nodes {
   356  	if id < uint64(len(l.s)) {
   357  		return l.s[id]
   358  	} else {
   359  		return l.m[id]
   360  	}
   361  }
   362  
   363  // CreateNodes creates graph nodes for all locations in a profile. It
   364  // returns set of all nodes, plus a mapping of each location to the
   365  // set of corresponding nodes (one per location.Line).
   366  func CreateNodes(prof *Profile, o *Options) (Nodes, locationMap) {
   367  	locations := locationMap{make([]Nodes, len(prof.Location)+1), make(map[uint64]Nodes)}
   368  	nm := make(NodeMap, len(prof.Location))
   369  	for _, l := range prof.Location {
   370  		lines := l.Line
   371  		if len(lines) == 0 {
   372  			lines = []Line{{}} // Create empty line to include location info.
   373  		}
   374  		nodes := make(Nodes, len(lines))
   375  		for ln := range lines {
   376  			nodes[ln] = nm.findOrInsertLine(l, lines[ln], o)
   377  		}
   378  		locations.add(l.ID, nodes)
   379  	}
   380  	return nm.nodes(), locations
   381  }
   382  
   383  func (nm NodeMap) nodes() Nodes {
   384  	nodes := make(Nodes, 0, len(nm))
   385  	for _, n := range nm {
   386  		nodes = append(nodes, n)
   387  	}
   388  	return nodes
   389  }
   390  
   391  func (nm NodeMap) findOrInsertLine(l *Location, li Line, o *Options) *Node {
   392  	var objfile string
   393  	if m := l.Mapping; m != nil && m.File != "" {
   394  		objfile = m.File
   395  	}
   396  
   397  	if ni := nodeInfo(l, li, objfile, o); ni != nil {
   398  		return nm.FindOrInsertNode(*ni, o.KeptNodes)
   399  	}
   400  	return nil
   401  }
   402  
   403  func nodeInfo(l *Location, line Line, objfile string, o *Options) *NodeInfo {
   404  	if line.Function == nil {
   405  		return &NodeInfo{Address: l.Address}
   406  	}
   407  	ni := &NodeInfo{
   408  		Address: l.Address,
   409  		Lineno:  int(line.Line),
   410  		Name:    line.Function.Name,
   411  	}
   412  	ni.StartLine = int(line.Function.StartLine)
   413  	return ni
   414  }
   415  
   416  // Sum adds the flat and cum values of a set of nodes.
   417  func (ns Nodes) Sum() (flat int64, cum int64) {
   418  	for _, n := range ns {
   419  		flat += n.Flat
   420  		cum += n.Cum
   421  	}
   422  	return
   423  }
   424  
   425  func (n *Node) addSample(dw, w int64, flat bool) {
   426  	// Update sample value
   427  	if flat {
   428  		n.FlatDiv += dw
   429  		n.Flat += w
   430  	} else {
   431  		n.CumDiv += dw
   432  		n.Cum += w
   433  	}
   434  }
   435  
   436  // String returns a text representation of a graph, for debugging purposes.
   437  func (g *Graph) String() string {
   438  	var s []string
   439  
   440  	nodeIndex := make(map[*Node]int, len(g.Nodes))
   441  
   442  	for i, n := range g.Nodes {
   443  		nodeIndex[n] = i + 1
   444  	}
   445  
   446  	for i, n := range g.Nodes {
   447  		name := n.Info.PrintableName()
   448  		var in, out []int
   449  
   450  		for _, from := range n.In {
   451  			in = append(in, nodeIndex[from.Src])
   452  		}
   453  		for _, to := range n.Out {
   454  			out = append(out, nodeIndex[to.Dest])
   455  		}
   456  		s = append(s, fmt.Sprintf("%d: %s[flat=%d cum=%d] %x -> %v ", i+1, name, n.Flat, n.Cum, in, out))
   457  	}
   458  	return strings.Join(s, "\n")
   459  }
   460  
   461  // Sort returns a slice of the edges in the map, in a consistent
   462  // order. The sort order is first based on the edge weight
   463  // (higher-to-lower) and then by the node names to avoid flakiness.
   464  func (em EdgeMap) Sort() []*Edge {
   465  	el := make(edgeList, 0, len(em))
   466  	for _, w := range em {
   467  		el = append(el, w)
   468  	}
   469  
   470  	sort.Sort(el)
   471  	return el
   472  }
   473  
   474  // Sum returns the total weight for a set of nodes.
   475  func (em EdgeMap) Sum() int64 {
   476  	var ret int64
   477  	for _, edge := range em {
   478  		ret += edge.Weight
   479  	}
   480  	return ret
   481  }
   482  
   483  type edgeList []*Edge
   484  
   485  func (el edgeList) Len() int {
   486  	return len(el)
   487  }
   488  
   489  func (el edgeList) Less(i, j int) bool {
   490  	if el[i].Weight != el[j].Weight {
   491  		return abs64(el[i].Weight) > abs64(el[j].Weight)
   492  	}
   493  
   494  	from1 := el[i].Src.Info.PrintableName()
   495  	from2 := el[j].Src.Info.PrintableName()
   496  	if from1 != from2 {
   497  		return from1 < from2
   498  	}
   499  
   500  	to1 := el[i].Dest.Info.PrintableName()
   501  	to2 := el[j].Dest.Info.PrintableName()
   502  
   503  	return to1 < to2
   504  }
   505  
   506  func (el edgeList) Swap(i, j int) {
   507  	el[i], el[j] = el[j], el[i]
   508  }
   509  
   510  func abs64(i int64) int64 {
   511  	if i < 0 {
   512  		return -i
   513  	}
   514  	return i
   515  }
   516
View as plain text