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 graph collects a set of samples into a directed graph.
    16  package graph
    17  
    18  import (
    19  	"fmt"
    20  	"math"
    21  	"path/filepath"
    22  	"regexp"
    23  	"sort"
    24  	"strconv"
    25  	"strings"
    26  
    27  	"github.com/google/pprof/profile"
    28  )
    29  
    30  var (
    31  	// Removes package name and method arguments for Java method names.
    32  	// See tests for examples.
    33  	javaRegExp = regexp.MustCompile(`^(?:[a-z]\w*\.)*([A-Z][\w\$]*\.(?:<init>|[a-z][\w\$]*(?:\$\d+)?))(?:(?:\()|$)`)
    34  	// Removes package name and method arguments for Go function names.
    35  	// See tests for examples.
    36  	goRegExp = regexp.MustCompile(`^(?:[\w\-\.]+\/)+([^.]+\..+)`)
    37  	// Removes potential module versions in a package path.
    38  	goVerRegExp = regexp.MustCompile(`^(.*?)/v(?:[2-9]|[1-9][0-9]+)([./].*)$`)
    39  	// Strips C++ namespace prefix from a C++ function / method name.
    40  	// NOTE: Make sure to keep the template parameters in the name. Normally,
    41  	// template parameters are stripped from the C++ names but when
    42  	// -symbolize=demangle=templates flag is used, they will not be.
    43  	// See tests for examples.
    44  	cppRegExp                = regexp.MustCompile(`^(?:[_a-zA-Z]\w*::)+(_*[A-Z]\w*::~?[_a-zA-Z]\w*(?:<.*>)?)`)
    45  	cppAnonymousPrefixRegExp = regexp.MustCompile(`^\(anonymous namespace\)::`)
    46  )
    47  
    48  // Graph summarizes a performance profile into a format that is
    49  // suitable for visualization.
    50  type Graph struct {
    51  	Nodes Nodes
    52  }
    53  
    54  // Options encodes the options for constructing a graph
    55  type Options struct {
    56  	SampleValue       func(s []int64) int64      // Function to compute the value of a sample
    57  	SampleMeanDivisor func(s []int64) int64      // Function to compute the divisor for mean graphs, or nil
    58  	FormatTag         func(int64, string) string // Function to format a sample tag value into a string
    59  	ObjNames          bool                       // Always preserve obj filename
    60  	OrigFnNames       bool                       // Preserve original (eg mangled) function names
    61  
    62  	CallTree     bool // Build a tree instead of a graph
    63  	DropNegative bool // Drop nodes with overall negative values
    64  
    65  	KeptNodes NodeSet // If non-nil, only use nodes in this set
    66  }
    67  
    68  // Nodes is an ordered collection of graph nodes.
    69  type Nodes []*Node
    70  
    71  // Node is an entry on a profiling report. It represents a unique
    72  // program location.
    73  type Node struct {
    74  	// Info describes the source location associated to this node.
    75  	Info NodeInfo
    76  
    77  	// Function represents the function that this node belongs to. On
    78  	// graphs with sub-function resolution (eg line number or
    79  	// addresses), two nodes in a NodeMap that are part of the same
    80  	// function have the same value of Node.Function. If the Node
    81  	// represents the whole function, it points back to itself.
    82  	Function *Node
    83  
    84  	// Values associated to this node. Flat is exclusive to this node,
    85  	// Cum includes all descendents.
    86  	Flat, FlatDiv, Cum, CumDiv int64
    87  
    88  	// In and out Contains the nodes immediately reaching or reached by
    89  	// this node.
    90  	In, Out EdgeMap
    91  
    92  	// LabelTags provide additional information about subsets of a sample.
    93  	LabelTags TagMap
    94  
    95  	// NumericTags provide additional values for subsets of a sample.
    96  	// Numeric tags are optionally associated to a label tag. The key
    97  	// for NumericTags is the name of the LabelTag they are associated
    98  	// to, or "" for numeric tags not associated to a label tag.
    99  	NumericTags map[string]TagMap
   100  }
   101  
   102  // FlatValue returns the exclusive value for this node, computing the
   103  // mean if a divisor is available.
   104  func (n *Node) FlatValue() int64 {
   105  	if n.FlatDiv == 0 {
   106  		return n.Flat
   107  	}
   108  	return n.Flat / n.FlatDiv
   109  }
   110  
   111  // CumValue returns the inclusive value for this node, computing the
   112  // mean if a divisor is available.
   113  func (n *Node) CumValue() int64 {
   114  	if n.CumDiv == 0 {
   115  		return n.Cum
   116  	}
   117  	return n.Cum / n.CumDiv
   118  }
   119  
   120  // AddToEdge increases the weight of an edge between two nodes. If
   121  // there isn't such an edge one is created.
   122  func (n *Node) AddToEdge(to *Node, v int64, residual, inline bool) {
   123  	n.AddToEdgeDiv(to, 0, v, residual, inline)
   124  }
   125  
   126  // AddToEdgeDiv increases the weight of an edge between two nodes. If
   127  // there isn't such an edge one is created.
   128  func (n *Node) AddToEdgeDiv(to *Node, dv, v int64, residual, inline bool) {
   129  	if n.Out[to] != to.In[n] {
   130  		panic(fmt.Errorf("asymmetric edges %v %v", *n, *to))
   131  	}
   132  
   133  	if e := n.Out[to]; e != nil {
   134  		e.WeightDiv += dv
   135  		e.Weight += v
   136  		if residual {
   137  			e.Residual = true
   138  		}
   139  		if !inline {
   140  			e.Inline = false
   141  		}
   142  		return
   143  	}
   144  
   145  	info := &Edge{Src: n, Dest: to, WeightDiv: dv, Weight: v, Residual: residual, Inline: inline}
   146  	n.Out[to] = info
   147  	to.In[n] = info
   148  }
   149  
   150  // NodeInfo contains the attributes for a node.
   151  type NodeInfo struct {
   152  	Name              string
   153  	OrigName          string
   154  	Address           uint64
   155  	File              string
   156  	StartLine, Lineno int
   157  	Columnno          int
   158  	Objfile           string
   159  }
   160  
   161  // PrintableName calls the Node's Formatter function with a single space separator.
   162  func (i *NodeInfo) PrintableName() string {
   163  	return strings.Join(i.NameComponents(), " ")
   164  }
   165  
   166  // NameComponents returns the components of the printable name to be used for a node.
   167  func (i *NodeInfo) NameComponents() []string {
   168  	var name []string
   169  	if i.Address != 0 {
   170  		name = append(name, fmt.Sprintf("%016x", i.Address))
   171  	}
   172  	if fun := i.Name; fun != "" {
   173  		name = append(name, fun)
   174  	}
   175  
   176  	switch {
   177  	case i.Lineno != 0:
   178  		s := fmt.Sprintf("%s:%d", i.File, i.Lineno)
   179  		if i.Columnno != 0 {
   180  			s += fmt.Sprintf(":%d", i.Columnno)
   181  		}
   182  		// User requested line numbers, provide what we have.
   183  		name = append(name, s)
   184  	case i.File != "":
   185  		// User requested file name, provide it.
   186  		name = append(name, i.File)
   187  	case i.Name != "":
   188  		// User requested function name. It was already included.
   189  	case i.Objfile != "":
   190  		// Only binary name is available
   191  		name = append(name, "["+filepath.Base(i.Objfile)+"]")
   192  	default:
   193  		// Do not leave it empty if there is no information at all.
   194  		name = append(name, "<unknown>")
   195  	}
   196  	return name
   197  }
   198  
   199  // comparePrintableName compares NodeInfo lexicographically the same way as `i.PrintableName() < right.PrintableName()`, but much more performant.
   200  func (i *NodeInfo) comparePrintableName(right NodeInfo) (equal bool, less bool) {
   201  	if right == *i {
   202  		return true, false
   203  	}
   204  
   205  	if i.Address != 0 && right.Address != 0 && i.Address != right.Address {
   206  		// comparing ints directly is the same as comparing padded hex from fmt.Sprintf("%016x", Address)
   207  		return false, i.Address < right.Address
   208  	}
   209  
   210  	// fallback
   211  	return false, i.PrintableName() < right.PrintableName()
   212  }
   213  
   214  // NodeMap maps from a node info struct to a node. It is used to merge
   215  // report entries with the same info.
   216  type NodeMap map[NodeInfo]*Node
   217  
   218  // NodeSet is a collection of node info structs.
   219  type NodeSet map[NodeInfo]bool
   220  
   221  // NodePtrSet is a collection of nodes. Trimming a graph or tree requires a set
   222  // of objects which uniquely identify the nodes to keep. In a graph, NodeInfo
   223  // works as a unique identifier; however, in a tree multiple nodes may share
   224  // identical NodeInfos. A *Node does uniquely identify a node so we can use that
   225  // instead. Though a *Node also uniquely identifies a node in a graph,
   226  // currently, during trimming, graphs are rebuilt from scratch using only the
   227  // NodeSet, so there would not be the required context of the initial graph to
   228  // allow for the use of *Node.
   229  type NodePtrSet map[*Node]bool
   230  
   231  // FindOrInsertNode takes the info for a node and either returns a matching node
   232  // from the node map if one exists, or adds one to the map if one does not.
   233  // If kept is non-nil, nodes are only added if they can be located on it.
   234  func (nm NodeMap) FindOrInsertNode(info NodeInfo, kept NodeSet) *Node {
   235  	if kept != nil {
   236  		if _, ok := kept[info]; !ok {
   237  			return nil
   238  		}
   239  	}
   240  
   241  	if n, ok := nm[info]; ok {
   242  		return n
   243  	}
   244  
   245  	n := &Node{
   246  		Info:        info,
   247  		In:          make(EdgeMap),
   248  		Out:         make(EdgeMap),
   249  		LabelTags:   make(TagMap),
   250  		NumericTags: make(map[string]TagMap),
   251  	}
   252  	nm[info] = n
   253  	if info.Address == 0 && info.Lineno == 0 {
   254  		// This node represents the whole function, so point Function
   255  		// back to itself.
   256  		n.Function = n
   257  		return n
   258  	}
   259  	// Find a node that represents the whole function.
   260  	info.Address = 0
   261  	info.Lineno = 0
   262  	info.Columnno = 0
   263  	n.Function = nm.FindOrInsertNode(info, nil)
   264  	return n
   265  }
   266  
   267  // EdgeMap is used to represent the incoming/outgoing edges from a node.
   268  type EdgeMap map[*Node]*Edge
   269  
   270  // Edge contains any attributes to be represented about edges in a graph.
   271  type Edge struct {
   272  	Src, Dest *Node
   273  	// The summary weight of the edge
   274  	Weight, WeightDiv int64
   275  
   276  	// residual edges connect nodes that were connected through a
   277  	// separate node, which has been removed from the report.
   278  	Residual bool
   279  	// An inline edge represents a call that was inlined into the caller.
   280  	Inline bool
   281  }
   282  
   283  // WeightValue returns the weight value for this edge, normalizing if a
   284  // divisor is available.
   285  func (e *Edge) WeightValue() int64 {
   286  	if e.WeightDiv == 0 {
   287  		return e.Weight
   288  	}
   289  	return e.Weight / e.WeightDiv
   290  }
   291  
   292  // Tag represent sample annotations
   293  type Tag struct {
   294  	Name          string
   295  	Unit          string // Describe the value, "" for non-numeric tags
   296  	Value         int64
   297  	Flat, FlatDiv int64
   298  	Cum, CumDiv   int64
   299  }
   300  
   301  // FlatValue returns the exclusive value for this tag, computing the
   302  // mean if a divisor is available.
   303  func (t *Tag) FlatValue() int64 {
   304  	if t.FlatDiv == 0 {
   305  		return t.Flat
   306  	}
   307  	return t.Flat / t.FlatDiv
   308  }
   309  
   310  // CumValue returns the inclusive value for this tag, computing the
   311  // mean if a divisor is available.
   312  func (t *Tag) CumValue() int64 {
   313  	if t.CumDiv == 0 {
   314  		return t.Cum
   315  	}
   316  	return t.Cum / t.CumDiv
   317  }
   318  
   319  // TagMap is a collection of tags, classified by their name.
   320  type TagMap map[string]*Tag
   321  
   322  // SortTags sorts a slice of tags based on their weight.
   323  func SortTags(t []*Tag, flat bool) []*Tag {
   324  	ts := tags{t, flat}
   325  	sort.Sort(ts)
   326  	return ts.t
   327  }
   328  
   329  // New summarizes performance data from a profile into a graph.
   330  func New(prof *profile.Profile, o *Options) *Graph {
   331  	if o.CallTree {
   332  		return newTree(prof, o)
   333  	}
   334  	g, _ := newGraph(prof, o)
   335  	return g
   336  }
   337  
   338  // newGraph computes a graph from a profile. It returns the graph, and
   339  // a map from the profile location indices to the corresponding graph
   340  // nodes.
   341  func newGraph(prof *profile.Profile, o *Options) (*Graph, map[uint64]Nodes) {
   342  	nodes, locationMap := CreateNodes(prof, o)
   343  	seenNode := make(map[*Node]bool)
   344  	seenEdge := make(map[nodePair]bool)
   345  	for _, sample := range prof.Sample {
   346  		var w, dw int64
   347  		w = o.SampleValue(sample.Value)
   348  		if o.SampleMeanDivisor != nil {
   349  			dw = o.SampleMeanDivisor(sample.Value)
   350  		}
   351  		if dw == 0 && w == 0 {
   352  			continue
   353  		}
   354  		clear(seenNode)
   355  		clear(seenEdge)
   356  		var parent *Node
   357  		// A residual edge goes over one or more nodes that were not kept.
   358  		residual := false
   359  
   360  		labels := joinLabels(sample)
   361  		// Group the sample frames, based on a global map.
   362  		for i := len(sample.Location) - 1; i >= 0; i-- {
   363  			l := sample.Location[i]
   364  			locNodes := locationMap[l.ID]
   365  			for ni := len(locNodes) - 1; ni >= 0; ni-- {
   366  				n := locNodes[ni]
   367  				if n == nil {
   368  					residual = true
   369  					continue
   370  				}
   371  				// Add cum weight to all nodes in stack, avoiding double counting.
   372  				if _, ok := seenNode[n]; !ok {
   373  					seenNode[n] = true
   374  					n.addSample(dw, w, labels, sample.NumLabel, sample.NumUnit, o.FormatTag, false)
   375  				}
   376  				// Update edge weights for all edges in stack, avoiding double counting.
   377  				if _, ok := seenEdge[nodePair{n, parent}]; !ok && parent != nil && n != parent {
   378  					seenEdge[nodePair{n, parent}] = true
   379  					parent.AddToEdgeDiv(n, dw, w, residual, ni != len(locNodes)-1)
   380  				}
   381  				parent = n
   382  				residual = false
   383  			}
   384  		}
   385  		if parent != nil && !residual {
   386  			// Add flat weight to leaf node.
   387  			parent.addSample(dw, w, labels, sample.NumLabel, sample.NumUnit, o.FormatTag, true)
   388  		}
   389  	}
   390  
   391  	return selectNodesForGraph(nodes, o.DropNegative), locationMap
   392  }
   393  
   394  func selectNodesForGraph(nodes Nodes, dropNegative bool) *Graph {
   395  	// Collect nodes into a graph.
   396  	gNodes := make(Nodes, 0, len(nodes))
   397  	for _, n := range nodes {
   398  		if n == nil {
   399  			continue
   400  		}
   401  		if n.Cum == 0 && n.Flat == 0 {
   402  			continue
   403  		}
   404  		if dropNegative && isNegative(n) {
   405  			continue
   406  		}
   407  		gNodes = append(gNodes, n)
   408  	}
   409  	return &Graph{gNodes}
   410  }
   411  
   412  type nodePair struct {
   413  	src, dest *Node
   414  }
   415  
   416  func newTree(prof *profile.Profile, o *Options) (g *Graph) {
   417  	parentNodeMap := make(map[*Node]NodeMap, len(prof.Sample))
   418  	for _, sample := range prof.Sample {
   419  		var w, dw int64
   420  		w = o.SampleValue(sample.Value)
   421  		if o.SampleMeanDivisor != nil {
   422  			dw = o.SampleMeanDivisor(sample.Value)
   423  		}
   424  		if dw == 0 && w == 0 {
   425  			continue
   426  		}
   427  		var parent *Node
   428  		labels := joinLabels(sample)
   429  		// Group the sample frames, based on a per-node map.
   430  		for i := len(sample.Location) - 1; i >= 0; i-- {
   431  			l := sample.Location[i]
   432  			lines := l.Line
   433  			if len(lines) == 0 {
   434  				lines = []profile.Line{{}} // Create empty line to include location info.
   435  			}
   436  			for lidx := len(lines) - 1; lidx >= 0; lidx-- {
   437  				nodeMap := parentNodeMap[parent]
   438  				if nodeMap == nil {
   439  					nodeMap = make(NodeMap)
   440  					parentNodeMap[parent] = nodeMap
   441  				}
   442  				n := nodeMap.findOrInsertLine(l, lines[lidx], o)
   443  				if n == nil {
   444  					continue
   445  				}
   446  				n.addSample(dw, w, labels, sample.NumLabel, sample.NumUnit, o.FormatTag, false)
   447  				if parent != nil {
   448  					parent.AddToEdgeDiv(n, dw, w, false, lidx != len(lines)-1)
   449  				}
   450  				parent = n
   451  			}
   452  		}
   453  		if parent != nil {
   454  			parent.addSample(dw, w, labels, sample.NumLabel, sample.NumUnit, o.FormatTag, true)
   455  		}
   456  	}
   457  
   458  	nodes := make(Nodes, 0, len(prof.Location))
   459  	for _, nm := range parentNodeMap {
   460  		nodes = append(nodes, nm.nodes()...)
   461  	}
   462  	return selectNodesForGraph(nodes, o.DropNegative)
   463  }
   464  
   465  // ShortenFunctionName returns a shortened version of a function's name.
   466  func ShortenFunctionName(f string) string {
   467  	f = cppAnonymousPrefixRegExp.ReplaceAllString(f, "")
   468  	f = goVerRegExp.ReplaceAllString(f, `${1}${2}`)
   469  	for _, re := range []*regexp.Regexp{goRegExp, javaRegExp, cppRegExp} {
   470  		if matches := re.FindStringSubmatch(f); len(matches) >= 2 {
   471  			return strings.Join(matches[1:], "")
   472  		}
   473  	}
   474  	return f
   475  }
   476  
   477  // TrimTree trims a Graph in forest form, keeping only the nodes in kept. This
   478  // will not work correctly if even a single node has multiple parents.
   479  func (g *Graph) TrimTree(kept NodePtrSet) {
   480  	// Creates a new list of nodes
   481  	oldNodes := g.Nodes
   482  	g.Nodes = make(Nodes, 0, len(kept))
   483  
   484  	for _, cur := range oldNodes {
   485  		// A node may not have multiple parents
   486  		if len(cur.In) > 1 {
   487  			panic("TrimTree only works on trees")
   488  		}
   489  
   490  		// If a node should be kept, add it to the new list of nodes
   491  		if _, ok := kept[cur]; ok {
   492  			g.Nodes = append(g.Nodes, cur)
   493  			continue
   494  		}
   495  
   496  		// If a node has no parents, then delete all of the in edges of its
   497  		// children to make them each roots of their own trees.
   498  		if len(cur.In) == 0 {
   499  			for _, outEdge := range cur.Out {
   500  				delete(outEdge.Dest.In, cur)
   501  			}
   502  			continue
   503  		}
   504  
   505  		// Get the parent. This works since at this point cur.In must contain only
   506  		// one element.
   507  		if len(cur.In) != 1 {
   508  			panic("Get parent assertion failed. cur.In expected to be of length 1.")
   509  		}
   510  		var parent *Node
   511  		for _, edge := range cur.In {
   512  			parent = edge.Src
   513  		}
   514  
   515  		parentEdgeInline := parent.Out[cur].Inline
   516  
   517  		// Remove the edge from the parent to this node
   518  		delete(parent.Out, cur)
   519  
   520  		// Reconfigure every edge from the current node to now begin at the parent.
   521  		for _, outEdge := range cur.Out {
   522  			child := outEdge.Dest
   523  
   524  			delete(child.In, cur)
   525  			child.In[parent] = outEdge
   526  			parent.Out[child] = outEdge
   527  
   528  			outEdge.Src = parent
   529  			outEdge.Residual = true
   530  			// If the edge from the parent to the current node and the edge from the
   531  			// current node to the child are both inline, then this resulting residual
   532  			// edge should also be inline
   533  			outEdge.Inline = parentEdgeInline && outEdge.Inline
   534  		}
   535  	}
   536  	g.RemoveRedundantEdges()
   537  }
   538  
   539  func joinLabels(s *profile.Sample) string {
   540  	if len(s.Label) == 0 {
   541  		return ""
   542  	}
   543  
   544  	var labels []string
   545  	for key, vals := range s.Label {
   546  		for _, v := range vals {
   547  			labels = append(labels, key+":"+v)
   548  		}
   549  	}
   550  	sort.Strings(labels)
   551  	return strings.Join(labels, `\n`)
   552  }
   553  
   554  // isNegative returns true if the node is considered as "negative" for the
   555  // purposes of drop_negative.
   556  func isNegative(n *Node) bool {
   557  	switch {
   558  	case n.Flat < 0:
   559  		return true
   560  	case n.Flat == 0 && n.Cum < 0:
   561  		return true
   562  	default:
   563  		return false
   564  	}
   565  }
   566  
   567  // CreateNodes creates graph nodes for all locations in a profile. It
   568  // returns set of all nodes, plus a mapping of each location to the
   569  // set of corresponding nodes (one per location.Line).
   570  func CreateNodes(prof *profile.Profile, o *Options) (Nodes, map[uint64]Nodes) {
   571  	locations := make(map[uint64]Nodes, len(prof.Location))
   572  	nm := make(NodeMap, len(prof.Location))
   573  	for _, l := range prof.Location {
   574  		lines := l.Line
   575  		if len(lines) == 0 {
   576  			lines = []profile.Line{{}} // Create empty line to include location info.
   577  		}
   578  		nodes := make(Nodes, len(lines))
   579  		for ln := range lines {
   580  			nodes[ln] = nm.findOrInsertLine(l, lines[ln], o)
   581  		}
   582  		locations[l.ID] = nodes
   583  	}
   584  	return nm.nodes(), locations
   585  }
   586  
   587  func (nm NodeMap) nodes() Nodes {
   588  	nodes := make(Nodes, 0, len(nm))
   589  	for _, n := range nm {
   590  		nodes = append(nodes, n)
   591  	}
   592  	return nodes
   593  }
   594  
   595  func (nm NodeMap) findOrInsertLine(l *profile.Location, li profile.Line, o *Options) *Node {
   596  	var objfile string
   597  	if m := l.Mapping; m != nil && m.File != "" {
   598  		objfile = m.File
   599  	}
   600  
   601  	ni := nodeInfo(l, li, objfile, o)
   602  
   603  	return nm.FindOrInsertNode(ni, o.KeptNodes)
   604  }
   605  
   606  func nodeInfo(l *profile.Location, line profile.Line, objfile string, o *Options) NodeInfo {
   607  	if line.Function == nil {
   608  		return NodeInfo{Address: l.Address, Objfile: objfile}
   609  	}
   610  	ni := NodeInfo{
   611  		Address:  l.Address,
   612  		Lineno:   int(line.Line),
   613  		Columnno: int(line.Column),
   614  		Name:     line.Function.Name,
   615  	}
   616  	if fname := line.Function.Filename; fname != "" {
   617  		ni.File = filepath.Clean(fname)
   618  	}
   619  	if o.OrigFnNames {
   620  		ni.OrigName = line.Function.SystemName
   621  	}
   622  	if o.ObjNames || (ni.Name == "" && ni.OrigName == "") {
   623  		ni.Objfile = objfile
   624  		ni.StartLine = int(line.Function.StartLine)
   625  	}
   626  	return ni
   627  }
   628  
   629  type tags struct {
   630  	t    []*Tag
   631  	flat bool
   632  }
   633  
   634  func (t tags) Len() int      { return len(t.t) }
   635  func (t tags) Swap(i, j int) { t.t[i], t.t[j] = t.t[j], t.t[i] }
   636  func (t tags) Less(i, j int) bool {
   637  	if !t.flat {
   638  		if t.t[i].Cum != t.t[j].Cum {
   639  			return abs64(t.t[i].Cum) > abs64(t.t[j].Cum)
   640  		}
   641  	}
   642  	if t.t[i].Flat != t.t[j].Flat {
   643  		return abs64(t.t[i].Flat) > abs64(t.t[j].Flat)
   644  	}
   645  	return t.t[i].Name < t.t[j].Name
   646  }
   647  
   648  // Sum adds the flat and cum values of a set of nodes.
   649  func (ns Nodes) Sum() (flat int64, cum int64) {
   650  	for _, n := range ns {
   651  		flat += n.Flat
   652  		cum += n.Cum
   653  	}
   654  	return
   655  }
   656  
   657  func (n *Node) addSample(dw, w int64, labels string, numLabel map[string][]int64, numUnit map[string][]string, format func(int64, string) string, flat bool) {
   658  	// Update sample value
   659  	if flat {
   660  		n.FlatDiv += dw
   661  		n.Flat += w
   662  	} else {
   663  		n.CumDiv += dw
   664  		n.Cum += w
   665  	}
   666  
   667  	// Add string tags
   668  	if labels != "" {
   669  		t := n.LabelTags.findOrAddTag(labels, "", 0)
   670  		if flat {
   671  			t.FlatDiv += dw
   672  			t.Flat += w
   673  		} else {
   674  			t.CumDiv += dw
   675  			t.Cum += w
   676  		}
   677  	}
   678  
   679  	numericTags := n.NumericTags[labels]
   680  	if numericTags == nil {
   681  		numericTags = TagMap{}
   682  		n.NumericTags[labels] = numericTags
   683  	}
   684  	// Add numeric tags
   685  	if format == nil {
   686  		format = defaultLabelFormat
   687  	}
   688  	for k, nvals := range numLabel {
   689  		units := numUnit[k]
   690  		for i, v := range nvals {
   691  			var t *Tag
   692  			if len(units) > 0 {
   693  				t = numericTags.findOrAddTag(format(v, units[i]), units[i], v)
   694  			} else {
   695  				t = numericTags.findOrAddTag(format(v, k), k, v)
   696  			}
   697  			if flat {
   698  				t.FlatDiv += dw
   699  				t.Flat += w
   700  			} else {
   701  				t.CumDiv += dw
   702  				t.Cum += w
   703  			}
   704  		}
   705  	}
   706  }
   707  
   708  func defaultLabelFormat(v int64, key string) string {
   709  	return strconv.FormatInt(v, 10)
   710  }
   711  
   712  func (m TagMap) findOrAddTag(label, unit string, value int64) *Tag {
   713  	l := m[label]
   714  	if l == nil {
   715  		l = &Tag{
   716  			Name:  label,
   717  			Unit:  unit,
   718  			Value: value,
   719  		}
   720  		m[label] = l
   721  	}
   722  	return l
   723  }
   724  
   725  // String returns a text representation of a graph, for debugging purposes.
   726  func (g *Graph) String() string {
   727  	var s []string
   728  
   729  	nodeIndex := make(map[*Node]int, len(g.Nodes))
   730  
   731  	for i, n := range g.Nodes {
   732  		nodeIndex[n] = i + 1
   733  	}
   734  
   735  	for i, n := range g.Nodes {
   736  		name := n.Info.PrintableName()
   737  		var in, out []int
   738  
   739  		for _, from := range n.In {
   740  			in = append(in, nodeIndex[from.Src])
   741  		}
   742  		for _, to := range n.Out {
   743  			out = append(out, nodeIndex[to.Dest])
   744  		}
   745  		s = append(s, fmt.Sprintf("%d: %s[flat=%d cum=%d] %x -> %v ", i+1, name, n.Flat, n.Cum, in, out))
   746  	}
   747  	return strings.Join(s, "\n")
   748  }
   749  
   750  // DiscardLowFrequencyNodes returns a set of the nodes at or over a
   751  // specific cum value cutoff.
   752  func (g *Graph) DiscardLowFrequencyNodes(nodeCutoff int64) NodeSet {
   753  	return makeNodeSet(g.Nodes, nodeCutoff)
   754  }
   755  
   756  // DiscardLowFrequencyNodePtrs returns a NodePtrSet of nodes at or over a
   757  // specific cum value cutoff.
   758  func (g *Graph) DiscardLowFrequencyNodePtrs(nodeCutoff int64) NodePtrSet {
   759  	cutNodes := getNodesAboveCumCutoff(g.Nodes, nodeCutoff)
   760  	kept := make(NodePtrSet, len(cutNodes))
   761  	for _, n := range cutNodes {
   762  		kept[n] = true
   763  	}
   764  	return kept
   765  }
   766  
   767  func makeNodeSet(nodes Nodes, nodeCutoff int64) NodeSet {
   768  	cutNodes := getNodesAboveCumCutoff(nodes, nodeCutoff)
   769  	kept := make(NodeSet, len(cutNodes))
   770  	for _, n := range cutNodes {
   771  		kept[n.Info] = true
   772  	}
   773  	return kept
   774  }
   775  
   776  // getNodesAboveCumCutoff returns all the nodes which have a Cum value greater
   777  // than or equal to cutoff.
   778  func getNodesAboveCumCutoff(nodes Nodes, nodeCutoff int64) Nodes {
   779  	cutoffNodes := make(Nodes, 0, len(nodes))
   780  	for _, n := range nodes {
   781  		if abs64(n.Cum) < nodeCutoff {
   782  			continue
   783  		}
   784  		cutoffNodes = append(cutoffNodes, n)
   785  	}
   786  	return cutoffNodes
   787  }
   788  
   789  // TrimLowFrequencyTags removes tags that have less than
   790  // the specified weight.
   791  func (g *Graph) TrimLowFrequencyTags(tagCutoff int64) {
   792  	// Remove nodes with value <= total*nodeFraction
   793  	for _, n := range g.Nodes {
   794  		n.LabelTags = trimLowFreqTags(n.LabelTags, tagCutoff)
   795  		for s, nt := range n.NumericTags {
   796  			n.NumericTags[s] = trimLowFreqTags(nt, tagCutoff)
   797  		}
   798  	}
   799  }
   800  
   801  func trimLowFreqTags(tags TagMap, minValue int64) TagMap {
   802  	kept := TagMap{}
   803  	for s, t := range tags {
   804  		if abs64(t.Flat) >= minValue || abs64(t.Cum) >= minValue {
   805  			kept[s] = t
   806  		}
   807  	}
   808  	return kept
   809  }
   810  
   811  // TrimLowFrequencyEdges removes edges that have less than
   812  // the specified weight. Returns the number of edges removed
   813  func (g *Graph) TrimLowFrequencyEdges(edgeCutoff int64) int {
   814  	var droppedEdges int
   815  	for _, n := range g.Nodes {
   816  		for src, e := range n.In {
   817  			if abs64(e.Weight) < edgeCutoff {
   818  				delete(n.In, src)
   819  				delete(src.Out, n)
   820  				droppedEdges++
   821  			}
   822  		}
   823  	}
   824  	return droppedEdges
   825  }
   826  
   827  // SortNodes sorts the nodes in a graph based on a specific heuristic.
   828  func (g *Graph) SortNodes(cum bool, visualMode bool) {
   829  	// Sort nodes based on requested mode
   830  	switch {
   831  	case visualMode:
   832  		// Specialized sort to produce a more visually-interesting graph
   833  		g.Nodes.Sort(EntropyOrder)
   834  	case cum:
   835  		g.Nodes.Sort(CumNameOrder)
   836  	default:
   837  		g.Nodes.Sort(FlatNameOrder)
   838  	}
   839  }
   840  
   841  // SelectTopNodePtrs returns a set of the top maxNodes *Node in a graph.
   842  func (g *Graph) SelectTopNodePtrs(maxNodes int, visualMode bool) NodePtrSet {
   843  	set := make(NodePtrSet)
   844  	for _, node := range g.selectTopNodes(maxNodes, visualMode) {
   845  		set[node] = true
   846  	}
   847  	return set
   848  }
   849  
   850  // SelectTopNodes returns a set of the top maxNodes nodes in a graph.
   851  func (g *Graph) SelectTopNodes(maxNodes int, visualMode bool) NodeSet {
   852  	return makeNodeSet(g.selectTopNodes(maxNodes, visualMode), 0)
   853  }
   854  
   855  // selectTopNodes returns a slice of the top maxNodes nodes in a graph.
   856  func (g *Graph) selectTopNodes(maxNodes int, visualMode bool) Nodes {
   857  	if maxNodes > 0 {
   858  		if visualMode {
   859  			var count int
   860  			// If generating a visual graph, count tags as nodes. Update
   861  			// maxNodes to account for them.
   862  			for i, n := range g.Nodes {
   863  				tags := min(countTags(n), maxNodelets)
   864  				if count += tags + 1; count >= maxNodes {
   865  					maxNodes = i + 1
   866  					break
   867  				}
   868  			}
   869  		}
   870  	}
   871  	if maxNodes > len(g.Nodes) {
   872  		maxNodes = len(g.Nodes)
   873  	}
   874  	return g.Nodes[:maxNodes]
   875  }
   876  
   877  // countTags counts the tags with flat count. This underestimates the
   878  // number of tags being displayed, but in practice is close enough.
   879  func countTags(n *Node) int {
   880  	count := 0
   881  	for _, e := range n.LabelTags {
   882  		if e.Flat != 0 {
   883  			count++
   884  		}
   885  	}
   886  	for _, t := range n.NumericTags {
   887  		for _, e := range t {
   888  			if e.Flat != 0 {
   889  				count++
   890  			}
   891  		}
   892  	}
   893  	return count
   894  }
   895  
   896  // RemoveRedundantEdges removes residual edges if the destination can
   897  // be reached through another path. This is done to simplify the graph
   898  // while preserving connectivity.
   899  func (g *Graph) RemoveRedundantEdges() {
   900  	// Walk the nodes and outgoing edges in reverse order to prefer
   901  	// removing edges with the lowest weight.
   902  	for i := len(g.Nodes); i > 0; i-- {
   903  		n := g.Nodes[i-1]
   904  		in := n.In.Sort()
   905  		for j := len(in); j > 0; j-- {
   906  			e := in[j-1]
   907  			if !e.Residual {
   908  				// Do not remove edges heavier than a non-residual edge, to
   909  				// avoid potential confusion.
   910  				break
   911  			}
   912  			if isRedundantEdge(e) {
   913  				delete(e.Src.Out, e.Dest)
   914  				delete(e.Dest.In, e.Src)
   915  			}
   916  		}
   917  	}
   918  }
   919  
   920  // isRedundantEdge determines if there is a path that allows e.Src
   921  // to reach e.Dest after removing e.
   922  func isRedundantEdge(e *Edge) bool {
   923  	src, n := e.Src, e.Dest
   924  	seen := map[*Node]bool{n: true}
   925  	queue := Nodes{n}
   926  	for len(queue) > 0 {
   927  		n := queue[0]
   928  		queue = queue[1:]
   929  		for _, ie := range n.In {
   930  			if e == ie || seen[ie.Src] {
   931  				continue
   932  			}
   933  			if ie.Src == src {
   934  				return true
   935  			}
   936  			seen[ie.Src] = true
   937  			queue = append(queue, ie.Src)
   938  		}
   939  	}
   940  	return false
   941  }
   942  
   943  // nodeSorter is a mechanism used to allow a report to be sorted
   944  // in different ways.
   945  type nodeSorter struct {
   946  	rs   Nodes
   947  	less func(l, r *Node) bool
   948  }
   949  
   950  func (s nodeSorter) Len() int           { return len(s.rs) }
   951  func (s nodeSorter) Swap(i, j int)      { s.rs[i], s.rs[j] = s.rs[j], s.rs[i] }
   952  func (s nodeSorter) Less(i, j int) bool { return s.less(s.rs[i], s.rs[j]) }
   953  
   954  // Sort reorders a slice of nodes based on the specified ordering
   955  // criteria. The result is sorted in decreasing order for (absolute)
   956  // numeric quantities, alphabetically for text, and increasing for
   957  // addresses.
   958  func (ns Nodes) Sort(o NodeOrder) error {
   959  	var s nodeSorter
   960  
   961  	switch o {
   962  	case FlatNameOrder:
   963  		s = nodeSorter{ns,
   964  			func(l, r *Node) bool {
   965  				if iv, jv := abs64(l.Flat), abs64(r.Flat); iv != jv {
   966  					return iv > jv
   967  				}
   968  				equal, leftLess := l.Info.comparePrintableName(r.Info)
   969  				if !equal {
   970  					return leftLess
   971  				}
   972  				if iv, jv := abs64(l.Cum), abs64(r.Cum); iv != jv {
   973  					return iv > jv
   974  				}
   975  				return compareNodes(l, r)
   976  			},
   977  		}
   978  	case FlatCumNameOrder:
   979  		s = nodeSorter{ns,
   980  			func(l, r *Node) bool {
   981  				if iv, jv := abs64(l.Flat), abs64(r.Flat); iv != jv {
   982  					return iv > jv
   983  				}
   984  				if iv, jv := abs64(l.Cum), abs64(r.Cum); iv != jv {
   985  					return iv > jv
   986  				}
   987  				equal, leftLess := l.Info.comparePrintableName(r.Info)
   988  				if !equal {
   989  					return leftLess
   990  				}
   991  				return compareNodes(l, r)
   992  			},
   993  		}
   994  	case NameOrder:
   995  		s = nodeSorter{ns,
   996  			func(l, r *Node) bool {
   997  				if iv, jv := l.Info.Name, r.Info.Name; iv != jv {
   998  					return iv < jv
   999  				}
  1000  				return compareNodes(l, r)
  1001  			},
  1002  		}
  1003  	case FileOrder:
  1004  		s = nodeSorter{ns,
  1005  			func(l, r *Node) bool {
  1006  				if iv, jv := l.Info.File, r.Info.File; iv != jv {
  1007  					return iv < jv
  1008  				}
  1009  				if iv, jv := l.Info.StartLine, r.Info.StartLine; iv != jv {
  1010  					return iv < jv
  1011  				}
  1012  				return compareNodes(l, r)
  1013  			},
  1014  		}
  1015  	case AddressOrder:
  1016  		s = nodeSorter{ns,
  1017  			func(l, r *Node) bool {
  1018  				if iv, jv := l.Info.Address, r.Info.Address; iv != jv {
  1019  					return iv < jv
  1020  				}
  1021  				return compareNodes(l, r)
  1022  			},
  1023  		}
  1024  	case CumNameOrder, EntropyOrder:
  1025  		// Hold scoring for score-based ordering
  1026  		var score map[*Node]int64
  1027  		scoreOrder := func(l, r *Node) bool {
  1028  			if iv, jv := abs64(score[l]), abs64(score[r]); iv != jv {
  1029  				return iv > jv
  1030  			}
  1031  			equal, leftLess := l.Info.comparePrintableName(r.Info)
  1032  			if !equal {
  1033  				return leftLess
  1034  			}
  1035  			if iv, jv := abs64(l.Flat), abs64(r.Flat); iv != jv {
  1036  				return iv > jv
  1037  			}
  1038  			return compareNodes(l, r)
  1039  		}
  1040  
  1041  		switch o {
  1042  		case CumNameOrder:
  1043  			score = make(map[*Node]int64, len(ns))
  1044  			for _, n := range ns {
  1045  				score[n] = n.Cum
  1046  			}
  1047  			s = nodeSorter{ns, scoreOrder}
  1048  		case EntropyOrder:
  1049  			score = make(map[*Node]int64, len(ns))
  1050  			for _, n := range ns {
  1051  				score[n] = entropyScore(n)
  1052  			}
  1053  			s = nodeSorter{ns, scoreOrder}
  1054  		}
  1055  	default:
  1056  		return fmt.Errorf("report: unrecognized sort ordering: %d", o)
  1057  	}
  1058  	sort.Sort(s)
  1059  	return nil
  1060  }
  1061  
  1062  // compareNodes compares two nodes to provide a deterministic ordering
  1063  // between them. Two nodes cannot have the same Node.Info value.
  1064  func compareNodes(l, r *Node) bool {
  1065  	return fmt.Sprint(l.Info) < fmt.Sprint(r.Info)
  1066  }
  1067  
  1068  // entropyScore computes a score for a node representing how important
  1069  // it is to include this node on a graph visualization. It is used to
  1070  // sort the nodes and select which ones to display if we have more
  1071  // nodes than desired in the graph. This number is computed by looking
  1072  // at the flat and cum weights of the node and the incoming/outgoing
  1073  // edges. The fundamental idea is to penalize nodes that have a simple
  1074  // fallthrough from their incoming to the outgoing edge.
  1075  func entropyScore(n *Node) int64 {
  1076  	score := float64(0)
  1077  
  1078  	if len(n.In) == 0 {
  1079  		score++ // Favor entry nodes
  1080  	} else {
  1081  		score += edgeEntropyScore(n, n.In, 0)
  1082  	}
  1083  
  1084  	if len(n.Out) == 0 {
  1085  		score++ // Favor leaf nodes
  1086  	} else {
  1087  		score += edgeEntropyScore(n, n.Out, n.Flat)
  1088  	}
  1089  
  1090  	return int64(score*float64(n.Cum)) + n.Flat
  1091  }
  1092  
  1093  // edgeEntropyScore computes the entropy value for a set of edges
  1094  // coming in or out of a node. Entropy (as defined in information
  1095  // theory) refers to the amount of information encoded by the set of
  1096  // edges. A set of edges that have a more interesting distribution of
  1097  // samples gets a higher score.
  1098  func edgeEntropyScore(n *Node, edges EdgeMap, self int64) float64 {
  1099  	score := float64(0)
  1100  	total := self
  1101  	for _, e := range edges {
  1102  		if e.Weight > 0 {
  1103  			total += abs64(e.Weight)
  1104  		}
  1105  	}
  1106  	if total != 0 {
  1107  		for _, e := range edges {
  1108  			frac := float64(abs64(e.Weight)) / float64(total)
  1109  			score += -frac * math.Log2(frac)
  1110  		}
  1111  		if self > 0 {
  1112  			frac := float64(abs64(self)) / float64(total)
  1113  			score += -frac * math.Log2(frac)
  1114  		}
  1115  	}
  1116  	return score
  1117  }
  1118  
  1119  // NodeOrder sets the ordering for a Sort operation
  1120  type NodeOrder int
  1121  
  1122  // Sorting options for node sort.
  1123  const (
  1124  	FlatNameOrder NodeOrder = iota
  1125  	FlatCumNameOrder
  1126  	CumNameOrder
  1127  	NameOrder
  1128  	FileOrder
  1129  	AddressOrder
  1130  	EntropyOrder
  1131  )
  1132  
  1133  // Sort returns a slice of the edges in the map, in a consistent
  1134  // order. The sort order is first based on the edge weight
  1135  // (higher-to-lower) and then by the node names to avoid flakiness.
  1136  func (e EdgeMap) Sort() []*Edge {
  1137  	el := make(edgeList, 0, len(e))
  1138  	for _, w := range e {
  1139  		el = append(el, w)
  1140  	}
  1141  
  1142  	sort.Sort(el)
  1143  	return el
  1144  }
  1145  
  1146  // Sum returns the total weight for a set of nodes.
  1147  func (e EdgeMap) Sum() int64 {
  1148  	var ret int64
  1149  	for _, edge := range e {
  1150  		ret += edge.Weight
  1151  	}
  1152  	return ret
  1153  }
  1154  
  1155  type edgeList []*Edge
  1156  
  1157  func (el edgeList) Len() int {
  1158  	return len(el)
  1159  }
  1160  
  1161  func (el edgeList) Less(i, j int) bool {
  1162  	if el[i].Weight != el[j].Weight {
  1163  		return abs64(el[i].Weight) > abs64(el[j].Weight)
  1164  	}
  1165  
  1166  	from1 := el[i].Src.Info.PrintableName()
  1167  	from2 := el[j].Src.Info.PrintableName()
  1168  	if from1 != from2 {
  1169  		return from1 < from2
  1170  	}
  1171  
  1172  	to1 := el[i].Dest.Info.PrintableName()
  1173  	to2 := el[j].Dest.Info.PrintableName()
  1174  
  1175  	return to1 < to2
  1176  }
  1177  
  1178  func (el edgeList) Swap(i, j int) {
  1179  	el[i], el[j] = el[j], el[i]
  1180  }
  1181  
  1182  func abs64(i int64) int64 {
  1183  	if i < 0 {
  1184  		return -i
  1185  	}
  1186  	return i
  1187  }
  1188
View as plain text