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// Implements methods to remove frames from profiles.
16
17package profile
18
19import (
20	"fmt"
21	"regexp"
22	"strings"
23)
24
25var (
26	reservedNames = []string{"(anonymous namespace)", "operator()"}
27	bracketRx     = func() *regexp.Regexp {
28		var quotedNames []string
29		for _, name := range append(reservedNames, "(") {
30			quotedNames = append(quotedNames, regexp.QuoteMeta(name))
31		}
32		return regexp.MustCompile(strings.Join(quotedNames, "|"))
33	}()
34)
35
36// simplifyFunc does some primitive simplification of function names.
37func simplifyFunc(f string) string {
38	// Account for leading '.' on the PPC ELF v1 ABI.
39	funcName := strings.TrimPrefix(f, ".")
40	// Account for unsimplified names -- try  to remove the argument list by trimming
41	// starting from the first '(', but skipping reserved names that have '('.
42	for _, ind := range bracketRx.FindAllStringSubmatchIndex(funcName, -1) {
43		foundReserved := false
44		for _, res := range reservedNames {
45			if funcName[ind[0]:ind[1]] == res {
46				foundReserved = true
47				break
48			}
49		}
50		if !foundReserved {
51			funcName = funcName[:ind[0]]
52			break
53		}
54	}
55	return funcName
56}
57
58// Prune removes all nodes beneath a node matching dropRx, and not
59// matching keepRx. If the root node of a Sample matches, the sample
60// will have an empty stack.
61func (p *Profile) Prune(dropRx, keepRx *regexp.Regexp) {
62	prune := make(map[uint64]bool)
63	pruneBeneath := make(map[uint64]bool)
64
65	for _, loc := range p.Location {
66		var i int
67		for i = len(loc.Line) - 1; i >= 0; i-- {
68			if fn := loc.Line[i].Function; fn != nil && fn.Name != "" {
69				funcName := simplifyFunc(fn.Name)
70				if dropRx.MatchString(funcName) {
71					if keepRx == nil || !keepRx.MatchString(funcName) {
72						break
73					}
74				}
75			}
76		}
77
78		if i >= 0 {
79			// Found matching entry to prune.
80			pruneBeneath[loc.ID] = true
81
82			// Remove the matching location.
83			if i == len(loc.Line)-1 {
84				// Matched the top entry: prune the whole location.
85				prune[loc.ID] = true
86			} else {
87				loc.Line = loc.Line[i+1:]
88			}
89		}
90	}
91
92	// Prune locs from each Sample
93	for _, sample := range p.Sample {
94		// Scan from the root to the leaves to find the prune location.
95		// Do not prune frames before the first user frame, to avoid
96		// pruning everything.
97		foundUser := false
98		for i := len(sample.Location) - 1; i >= 0; i-- {
99			id := sample.Location[i].ID
100			if !prune[id] && !pruneBeneath[id] {
101				foundUser = true
102				continue
103			}
104			if !foundUser {
105				continue
106			}
107			if prune[id] {
108				sample.Location = sample.Location[i+1:]
109				break
110			}
111			if pruneBeneath[id] {
112				sample.Location = sample.Location[i:]
113				break
114			}
115		}
116	}
117}
118
119// RemoveUninteresting prunes and elides profiles using built-in
120// tables of uninteresting function names.
121func (p *Profile) RemoveUninteresting() error {
122	var keep, drop *regexp.Regexp
123	var err error
124
125	if p.DropFrames != "" {
126		if drop, err = regexp.Compile("^(" + p.DropFrames + ")$"); err != nil {
127			return fmt.Errorf("failed to compile regexp %s: %v", p.DropFrames, err)
128		}
129		if p.KeepFrames != "" {
130			if keep, err = regexp.Compile("^(" + p.KeepFrames + ")$"); err != nil {
131				return fmt.Errorf("failed to compile regexp %s: %v", p.KeepFrames, err)
132			}
133		}
134		p.Prune(drop, keep)
135	}
136	return nil
137}
138
139// PruneFrom removes all nodes beneath the lowest node matching dropRx, not including itself.
140//
141// Please see the example below to understand this method as well as
142// the difference from Prune method.
143//
144// A sample contains Location of [A,B,C,B,D] where D is the top frame and there's no inline.
145//
146// PruneFrom(A) returns [A,B,C,B,D] because there's no node beneath A.
147// Prune(A, nil) returns [B,C,B,D] by removing A itself.
148//
149// PruneFrom(B) returns [B,C,B,D] by removing all nodes beneath the first B when scanning from the bottom.
150// Prune(B, nil) returns [D] because a matching node is found by scanning from the root.
151func (p *Profile) PruneFrom(dropRx *regexp.Regexp) {
152	pruneBeneath := make(map[uint64]bool)
153
154	for _, loc := range p.Location {
155		for i := 0; i < len(loc.Line); i++ {
156			if fn := loc.Line[i].Function; fn != nil && fn.Name != "" {
157				funcName := simplifyFunc(fn.Name)
158				if dropRx.MatchString(funcName) {
159					// Found matching entry to prune.
160					pruneBeneath[loc.ID] = true
161					loc.Line = loc.Line[i:]
162					break
163				}
164			}
165		}
166	}
167
168	// Prune locs from each Sample
169	for _, sample := range p.Sample {
170		// Scan from the bottom leaf to the root to find the prune location.
171		for i, loc := range sample.Location {
172			if pruneBeneath[loc.ID] {
173				sample.Location = sample.Location[i:]
174				break
175			}
176		}
177	}
178}
179