Black Lives Matter. Support the Equal Justice Initiative.

Source file src/cmd/vendor/github.com/google/pprof/internal/graph/graph.go

Documentation: cmd/vendor/github.com/google/pprof/internal/graph

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

View as plain text