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

View as plain text