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