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