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 15package report 16 17import ( 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. 30type 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. 40type 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. 46type 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. 75type 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. 81func (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 104func (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 167func (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 180func (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