stacks.go

     1  // Copyright 2022 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 report
    16  
    17  import (
    18  	"crypto/sha256"
    19  	"encoding/binary"
    20  	"fmt"
    21  	"path/filepath"
    22  
    23  	"github.com/google/pprof/internal/measurement"
    24  	"github.com/google/pprof/profile"
    25  )
    26  
    27  // StackSet holds a set of stacks corresponding to a profile.
    28  //
    29  // Slices in StackSet and the types it contains are always non-nil,
    30  // which makes Javascript code that uses the JSON encoding less error-prone.
    31  type StackSet struct {
    32  	Total   int64         // Total value of the profile.
    33  	Scale   float64       // Multiplier to generate displayed value
    34  	Type    string        // Profile type. E.g., "cpu".
    35  	Unit    string        // One of "B", "s", "GCU", or "" (if unknown)
    36  	Stacks  []Stack       // List of stored stacks
    37  	Sources []StackSource // Mapping from source index to info
    38  	report  *Report
    39  }
    40  
    41  // Stack holds a single stack instance.
    42  type Stack struct {
    43  	Value   int64 // Total value for all samples of this stack.
    44  	Sources []int // Indices in StackSet.Sources (callers before callees).
    45  }
    46  
    47  // StackSource holds function/location info for a stack entry.
    48  type StackSource struct {
    49  	FullName   string
    50  	FileName   string
    51  	UniqueName string // Disambiguates functions with same names
    52  	Inlined    bool   // If true this source was inlined into its caller
    53  
    54  	// Alternative names to display (with decreasing lengths) to make text fit.
    55  	// Guaranteed to be non-empty.
    56  	Display []string
    57  
    58  	// Places holds the list of stack slots where this source occurs.
    59  	// In particular, if [a,b] is an element in Places,
    60  	// StackSet.Stacks[a].Sources[b] points to this source.
    61  	//
    62  	// No stack will be referenced twice in the Places slice for a given
    63  	// StackSource. In case of recursion, Places will contain the outer-most
    64  	// entry in the recursive stack. E.g., if stack S has source X at positions
    65  	// 4,6,9,10, the Places entry for X will contain [S,4].
    66  	Places []StackSlot
    67  
    68  	// Combined count of stacks where this source is the leaf.
    69  	Self int64
    70  
    71  	// Color number to use for this source.
    72  	// Colors with high numbers than supported may be treated as zero.
    73  	Color int
    74  }
    75  
    76  // StackSlot identifies a particular StackSlot.
    77  type StackSlot struct {
    78  	Stack int // Index in StackSet.Stacks
    79  	Pos   int // Index in Stack.Sources
    80  }
    81  
    82  // Stacks returns a StackSet for the profile in rpt.
    83  func (rpt *Report) Stacks() StackSet {
    84  	// Get scale for converting to default unit of the right type.
    85  	scale, unit := measurement.Scale(1, rpt.options.SampleUnit, "default")
    86  	if unit == "default" {
    87  		unit = ""
    88  	}
    89  	if rpt.options.Ratio > 0 {
    90  		scale *= rpt.options.Ratio
    91  	}
    92  	s := &StackSet{
    93  		Total:   rpt.total,
    94  		Scale:   scale,
    95  		Type:    rpt.options.SampleType,
    96  		Unit:    unit,
    97  		Stacks:  []Stack{},       // Ensure non-nil
    98  		Sources: []StackSource{}, // Ensure non-nil
    99  		report:  rpt,
   100  	}
   101  	s.makeInitialStacks(rpt)
   102  	s.fillPlaces()
   103  	return *s
   104  }
   105  
   106  func (s *StackSet) makeInitialStacks(rpt *Report) {
   107  	type key struct {
   108  		funcName string
   109  		fileName string
   110  		line     int64
   111  		column   int64
   112  		inlined  bool
   113  	}
   114  	srcs := map[key]int{} // Sources identified so far.
   115  	seenFunctions := map[string]bool{}
   116  	unknownIndex := 1
   117  
   118  	getSrc := func(line profile.Line, inlined bool) int {
   119  		fn := line.Function
   120  		if fn == nil {
   121  			fn = &profile.Function{Name: fmt.Sprintf("?%d?", unknownIndex)}
   122  			unknownIndex++
   123  		}
   124  
   125  		k := key{fn.Name, fn.Filename, line.Line, line.Column, inlined}
   126  		if i, ok := srcs[k]; ok {
   127  			return i
   128  		}
   129  
   130  		fileName := trimPath(fn.Filename, rpt.options.TrimPath, rpt.options.SourcePath)
   131  		x := StackSource{
   132  			FileName: fileName,
   133  			Inlined:  inlined,
   134  			Places:   []StackSlot{}, // Ensure Places is non-nil
   135  		}
   136  		if fn.Name != "" {
   137  			x.FullName = addLineInfo(fn.Name, line)
   138  			x.Display = shortNameList(x.FullName)
   139  			x.Color = pickColor(packageName(fn.Name))
   140  		} else { // Use file name, e.g., for file granularity display.
   141  			x.FullName = addLineInfo(fileName, line)
   142  			x.Display = fileNameSuffixes(x.FullName)
   143  			x.Color = pickColor(filepath.Dir(fileName))
   144  		}
   145  
   146  		if !seenFunctions[x.FullName] {
   147  			x.UniqueName = x.FullName
   148  			seenFunctions[x.FullName] = true
   149  		} else {
   150  			// Assign a different name so pivoting picks this function.
   151  			x.UniqueName = fmt.Sprint(x.FullName, "#", fn.ID)
   152  		}
   153  
   154  		s.Sources = append(s.Sources, x)
   155  		srcs[k] = len(s.Sources) - 1
   156  		return len(s.Sources) - 1
   157  	}
   158  
   159  	// Synthesized root location that will be placed at the beginning of each stack.
   160  	s.Sources = []StackSource{{
   161  		FullName: "root",
   162  		Display:  []string{"root"},
   163  		Places:   []StackSlot{},
   164  	}}
   165  
   166  	for _, sample := range rpt.prof.Sample {
   167  		value := rpt.options.SampleValue(sample.Value)
   168  		stack := Stack{Value: value, Sources: []int{0}} // Start with the root
   169  
   170  		// Note: we need to reverse the order in the produced stack.
   171  		for i := len(sample.Location) - 1; i >= 0; i-- {
   172  			loc := sample.Location[i]
   173  			for j := len(loc.Line) - 1; j >= 0; j-- {
   174  				line := loc.Line[j]
   175  				inlined := (j != len(loc.Line)-1)
   176  				stack.Sources = append(stack.Sources, getSrc(line, inlined))
   177  			}
   178  		}
   179  
   180  		leaf := stack.Sources[len(stack.Sources)-1]
   181  		s.Sources[leaf].Self += value
   182  		s.Stacks = append(s.Stacks, stack)
   183  	}
   184  }
   185  
   186  func (s *StackSet) fillPlaces() {
   187  	for i, stack := range s.Stacks {
   188  		seenSrcs := map[int]bool{}
   189  		for j, src := range stack.Sources {
   190  			if seenSrcs[src] {
   191  				continue
   192  			}
   193  			seenSrcs[src] = true
   194  			s.Sources[src].Places = append(s.Sources[src].Places, StackSlot{i, j})
   195  		}
   196  	}
   197  }
   198  
   199  // pickColor picks a color for key.
   200  func pickColor(key string) int {
   201  	const numColors = 1048576
   202  	h := sha256.Sum256([]byte(key))
   203  	index := binary.LittleEndian.Uint32(h[:])
   204  	return int(index % numColors)
   205  }
   206  
   207  // Legend returns the list of lines to display as the legend.
   208  func (s *StackSet) Legend() []string {
   209  	return reportLabels(s.report, s.report.total, len(s.Sources), len(s.Sources), 0, 0, false)
   210  }
   211  
   212  func addLineInfo(str string, line profile.Line) string {
   213  	if line.Column != 0 {
   214  		return fmt.Sprint(str, ":", line.Line, ":", line.Column)
   215  	}
   216  	if line.Line != 0 {
   217  		return fmt.Sprint(str, ":", line.Line)
   218  	}
   219  	return str
   220  }
   221
View as plain text