Source file src/pkg/cmd/vendor/github.com/google/pprof/profile/merge.go

     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
    16	
    17	import (
    18		"fmt"
    19		"sort"
    20		"strconv"
    21		"strings"
    22	)
    23	
    24	// Compact performs garbage collection on a profile to remove any
    25	// unreferenced fields. This is useful to reduce the size of a profile
    26	// after samples or locations have been removed.
    27	func (p *Profile) Compact() *Profile {
    28		p, _ = Merge([]*Profile{p})
    29		return p
    30	}
    31	
    32	// Merge merges all the profiles in profs into a single Profile.
    33	// Returns a new profile independent of the input profiles. The merged
    34	// profile is compacted to eliminate unused samples, locations,
    35	// functions and mappings. Profiles must have identical profile sample
    36	// and period types or the merge will fail. profile.Period of the
    37	// resulting profile will be the maximum of all profiles, and
    38	// profile.TimeNanos will be the earliest nonzero one.
    39	func Merge(srcs []*Profile) (*Profile, error) {
    40		if len(srcs) == 0 {
    41			return nil, fmt.Errorf("no profiles to merge")
    42		}
    43		p, err := combineHeaders(srcs)
    44		if err != nil {
    45			return nil, err
    46		}
    47	
    48		pm := &profileMerger{
    49			p:         p,
    50			samples:   make(map[sampleKey]*Sample, len(srcs[0].Sample)),
    51			locations: make(map[locationKey]*Location, len(srcs[0].Location)),
    52			functions: make(map[functionKey]*Function, len(srcs[0].Function)),
    53			mappings:  make(map[mappingKey]*Mapping, len(srcs[0].Mapping)),
    54		}
    55	
    56		for _, src := range srcs {
    57			// Clear the profile-specific hash tables
    58			pm.locationsByID = make(map[uint64]*Location, len(src.Location))
    59			pm.functionsByID = make(map[uint64]*Function, len(src.Function))
    60			pm.mappingsByID = make(map[uint64]mapInfo, len(src.Mapping))
    61	
    62			if len(pm.mappings) == 0 && len(src.Mapping) > 0 {
    63				// The Mapping list has the property that the first mapping
    64				// represents the main binary. Take the first Mapping we see,
    65				// otherwise the operations below will add mappings in an
    66				// arbitrary order.
    67				pm.mapMapping(src.Mapping[0])
    68			}
    69	
    70			for _, s := range src.Sample {
    71				if !isZeroSample(s) {
    72					pm.mapSample(s)
    73				}
    74			}
    75		}
    76	
    77		for _, s := range p.Sample {
    78			if isZeroSample(s) {
    79				// If there are any zero samples, re-merge the profile to GC
    80				// them.
    81				return Merge([]*Profile{p})
    82			}
    83		}
    84	
    85		return p, nil
    86	}
    87	
    88	// Normalize normalizes the source profile by multiplying each value in profile by the
    89	// ratio of the sum of the base profile's values of that sample type to the sum of the
    90	// source profile's value of that sample type.
    91	func (p *Profile) Normalize(pb *Profile) error {
    92	
    93		if err := p.compatible(pb); err != nil {
    94			return err
    95		}
    96	
    97		baseVals := make([]int64, len(p.SampleType))
    98		for _, s := range pb.Sample {
    99			for i, v := range s.Value {
   100				baseVals[i] += v
   101			}
   102		}
   103	
   104		srcVals := make([]int64, len(p.SampleType))
   105		for _, s := range p.Sample {
   106			for i, v := range s.Value {
   107				srcVals[i] += v
   108			}
   109		}
   110	
   111		normScale := make([]float64, len(baseVals))
   112		for i := range baseVals {
   113			if srcVals[i] == 0 {
   114				normScale[i] = 0.0
   115			} else {
   116				normScale[i] = float64(baseVals[i]) / float64(srcVals[i])
   117			}
   118		}
   119		p.ScaleN(normScale)
   120		return nil
   121	}
   122	
   123	func isZeroSample(s *Sample) bool {
   124		for _, v := range s.Value {
   125			if v != 0 {
   126				return false
   127			}
   128		}
   129		return true
   130	}
   131	
   132	type profileMerger struct {
   133		p *Profile
   134	
   135		// Memoization tables within a profile.
   136		locationsByID map[uint64]*Location
   137		functionsByID map[uint64]*Function
   138		mappingsByID  map[uint64]mapInfo
   139	
   140		// Memoization tables for profile entities.
   141		samples   map[sampleKey]*Sample
   142		locations map[locationKey]*Location
   143		functions map[functionKey]*Function
   144		mappings  map[mappingKey]*Mapping
   145	}
   146	
   147	type mapInfo struct {
   148		m      *Mapping
   149		offset int64
   150	}
   151	
   152	func (pm *profileMerger) mapSample(src *Sample) *Sample {
   153		s := &Sample{
   154			Location: make([]*Location, len(src.Location)),
   155			Value:    make([]int64, len(src.Value)),
   156			Label:    make(map[string][]string, len(src.Label)),
   157			NumLabel: make(map[string][]int64, len(src.NumLabel)),
   158			NumUnit:  make(map[string][]string, len(src.NumLabel)),
   159		}
   160		for i, l := range src.Location {
   161			s.Location[i] = pm.mapLocation(l)
   162		}
   163		for k, v := range src.Label {
   164			vv := make([]string, len(v))
   165			copy(vv, v)
   166			s.Label[k] = vv
   167		}
   168		for k, v := range src.NumLabel {
   169			u := src.NumUnit[k]
   170			vv := make([]int64, len(v))
   171			uu := make([]string, len(u))
   172			copy(vv, v)
   173			copy(uu, u)
   174			s.NumLabel[k] = vv
   175			s.NumUnit[k] = uu
   176		}
   177		// Check memoization table. Must be done on the remapped location to
   178		// account for the remapped mapping. Add current values to the
   179		// existing sample.
   180		k := s.key()
   181		if ss, ok := pm.samples[k]; ok {
   182			for i, v := range src.Value {
   183				ss.Value[i] += v
   184			}
   185			return ss
   186		}
   187		copy(s.Value, src.Value)
   188		pm.samples[k] = s
   189		pm.p.Sample = append(pm.p.Sample, s)
   190		return s
   191	}
   192	
   193	// key generates sampleKey to be used as a key for maps.
   194	func (sample *Sample) key() sampleKey {
   195		ids := make([]string, len(sample.Location))
   196		for i, l := range sample.Location {
   197			ids[i] = strconv.FormatUint(l.ID, 16)
   198		}
   199	
   200		labels := make([]string, 0, len(sample.Label))
   201		for k, v := range sample.Label {
   202			labels = append(labels, fmt.Sprintf("%q%q", k, v))
   203		}
   204		sort.Strings(labels)
   205	
   206		numlabels := make([]string, 0, len(sample.NumLabel))
   207		for k, v := range sample.NumLabel {
   208			numlabels = append(numlabels, fmt.Sprintf("%q%x%x", k, v, sample.NumUnit[k]))
   209		}
   210		sort.Strings(numlabels)
   211	
   212		return sampleKey{
   213			strings.Join(ids, "|"),
   214			strings.Join(labels, ""),
   215			strings.Join(numlabels, ""),
   216		}
   217	}
   218	
   219	type sampleKey struct {
   220		locations string
   221		labels    string
   222		numlabels string
   223	}
   224	
   225	func (pm *profileMerger) mapLocation(src *Location) *Location {
   226		if src == nil {
   227			return nil
   228		}
   229	
   230		if l, ok := pm.locationsByID[src.ID]; ok {
   231			pm.locationsByID[src.ID] = l
   232			return l
   233		}
   234	
   235		mi := pm.mapMapping(src.Mapping)
   236		l := &Location{
   237			ID:       uint64(len(pm.p.Location) + 1),
   238			Mapping:  mi.m,
   239			Address:  uint64(int64(src.Address) + mi.offset),
   240			Line:     make([]Line, len(src.Line)),
   241			IsFolded: src.IsFolded,
   242		}
   243		for i, ln := range src.Line {
   244			l.Line[i] = pm.mapLine(ln)
   245		}
   246		// Check memoization table. Must be done on the remapped location to
   247		// account for the remapped mapping ID.
   248		k := l.key()
   249		if ll, ok := pm.locations[k]; ok {
   250			pm.locationsByID[src.ID] = ll
   251			return ll
   252		}
   253		pm.locationsByID[src.ID] = l
   254		pm.locations[k] = l
   255		pm.p.Location = append(pm.p.Location, l)
   256		return l
   257	}
   258	
   259	// key generates locationKey to be used as a key for maps.
   260	func (l *Location) key() locationKey {
   261		key := locationKey{
   262			addr:     l.Address,
   263			isFolded: l.IsFolded,
   264		}
   265		if l.Mapping != nil {
   266			// Normalizes address to handle address space randomization.
   267			key.addr -= l.Mapping.Start
   268			key.mappingID = l.Mapping.ID
   269		}
   270		lines := make([]string, len(l.Line)*2)
   271		for i, line := range l.Line {
   272			if line.Function != nil {
   273				lines[i*2] = strconv.FormatUint(line.Function.ID, 16)
   274			}
   275			lines[i*2+1] = strconv.FormatInt(line.Line, 16)
   276		}
   277		key.lines = strings.Join(lines, "|")
   278		return key
   279	}
   280	
   281	type locationKey struct {
   282		addr, mappingID uint64
   283		lines           string
   284		isFolded        bool
   285	}
   286	
   287	func (pm *profileMerger) mapMapping(src *Mapping) mapInfo {
   288		if src == nil {
   289			return mapInfo{}
   290		}
   291	
   292		if mi, ok := pm.mappingsByID[src.ID]; ok {
   293			return mi
   294		}
   295	
   296		// Check memoization tables.
   297		mk := src.key()
   298		if m, ok := pm.mappings[mk]; ok {
   299			mi := mapInfo{m, int64(m.Start) - int64(src.Start)}
   300			pm.mappingsByID[src.ID] = mi
   301			return mi
   302		}
   303		m := &Mapping{
   304			ID:              uint64(len(pm.p.Mapping) + 1),
   305			Start:           src.Start,
   306			Limit:           src.Limit,
   307			Offset:          src.Offset,
   308			File:            src.File,
   309			BuildID:         src.BuildID,
   310			HasFunctions:    src.HasFunctions,
   311			HasFilenames:    src.HasFilenames,
   312			HasLineNumbers:  src.HasLineNumbers,
   313			HasInlineFrames: src.HasInlineFrames,
   314		}
   315		pm.p.Mapping = append(pm.p.Mapping, m)
   316	
   317		// Update memoization tables.
   318		pm.mappings[mk] = m
   319		mi := mapInfo{m, 0}
   320		pm.mappingsByID[src.ID] = mi
   321		return mi
   322	}
   323	
   324	// key generates encoded strings of Mapping to be used as a key for
   325	// maps.
   326	func (m *Mapping) key() mappingKey {
   327		// Normalize addresses to handle address space randomization.
   328		// Round up to next 4K boundary to avoid minor discrepancies.
   329		const mapsizeRounding = 0x1000
   330	
   331		size := m.Limit - m.Start
   332		size = size + mapsizeRounding - 1
   333		size = size - (size % mapsizeRounding)
   334		key := mappingKey{
   335			size:   size,
   336			offset: m.Offset,
   337		}
   338	
   339		switch {
   340		case m.BuildID != "":
   341			key.buildIDOrFile = m.BuildID
   342		case m.File != "":
   343			key.buildIDOrFile = m.File
   344		default:
   345			// A mapping containing neither build ID nor file name is a fake mapping. A
   346			// key with empty buildIDOrFile is used for fake mappings so that they are
   347			// treated as the same mapping during merging.
   348		}
   349		return key
   350	}
   351	
   352	type mappingKey struct {
   353		size, offset  uint64
   354		buildIDOrFile string
   355	}
   356	
   357	func (pm *profileMerger) mapLine(src Line) Line {
   358		ln := Line{
   359			Function: pm.mapFunction(src.Function),
   360			Line:     src.Line,
   361		}
   362		return ln
   363	}
   364	
   365	func (pm *profileMerger) mapFunction(src *Function) *Function {
   366		if src == nil {
   367			return nil
   368		}
   369		if f, ok := pm.functionsByID[src.ID]; ok {
   370			return f
   371		}
   372		k := src.key()
   373		if f, ok := pm.functions[k]; ok {
   374			pm.functionsByID[src.ID] = f
   375			return f
   376		}
   377		f := &Function{
   378			ID:         uint64(len(pm.p.Function) + 1),
   379			Name:       src.Name,
   380			SystemName: src.SystemName,
   381			Filename:   src.Filename,
   382			StartLine:  src.StartLine,
   383		}
   384		pm.functions[k] = f
   385		pm.functionsByID[src.ID] = f
   386		pm.p.Function = append(pm.p.Function, f)
   387		return f
   388	}
   389	
   390	// key generates a struct to be used as a key for maps.
   391	func (f *Function) key() functionKey {
   392		return functionKey{
   393			f.StartLine,
   394			f.Name,
   395			f.SystemName,
   396			f.Filename,
   397		}
   398	}
   399	
   400	type functionKey struct {
   401		startLine                  int64
   402		name, systemName, fileName string
   403	}
   404	
   405	// combineHeaders checks that all profiles can be merged and returns
   406	// their combined profile.
   407	func combineHeaders(srcs []*Profile) (*Profile, error) {
   408		for _, s := range srcs[1:] {
   409			if err := srcs[0].compatible(s); err != nil {
   410				return nil, err
   411			}
   412		}
   413	
   414		var timeNanos, durationNanos, period int64
   415		var comments []string
   416		seenComments := map[string]bool{}
   417		var defaultSampleType string
   418		for _, s := range srcs {
   419			if timeNanos == 0 || s.TimeNanos < timeNanos {
   420				timeNanos = s.TimeNanos
   421			}
   422			durationNanos += s.DurationNanos
   423			if period == 0 || period < s.Period {
   424				period = s.Period
   425			}
   426			for _, c := range s.Comments {
   427				if seen := seenComments[c]; !seen {
   428					comments = append(comments, c)
   429					seenComments[c] = true
   430				}
   431			}
   432			if defaultSampleType == "" {
   433				defaultSampleType = s.DefaultSampleType
   434			}
   435		}
   436	
   437		p := &Profile{
   438			SampleType: make([]*ValueType, len(srcs[0].SampleType)),
   439	
   440			DropFrames: srcs[0].DropFrames,
   441			KeepFrames: srcs[0].KeepFrames,
   442	
   443			TimeNanos:     timeNanos,
   444			DurationNanos: durationNanos,
   445			PeriodType:    srcs[0].PeriodType,
   446			Period:        period,
   447	
   448			Comments:          comments,
   449			DefaultSampleType: defaultSampleType,
   450		}
   451		copy(p.SampleType, srcs[0].SampleType)
   452		return p, nil
   453	}
   454	
   455	// compatible determines if two profiles can be compared/merged.
   456	// returns nil if the profiles are compatible; otherwise an error with
   457	// details on the incompatibility.
   458	func (p *Profile) compatible(pb *Profile) error {
   459		if !equalValueType(p.PeriodType, pb.PeriodType) {
   460			return fmt.Errorf("incompatible period types %v and %v", p.PeriodType, pb.PeriodType)
   461		}
   462	
   463		if len(p.SampleType) != len(pb.SampleType) {
   464			return fmt.Errorf("incompatible sample types %v and %v", p.SampleType, pb.SampleType)
   465		}
   466	
   467		for i := range p.SampleType {
   468			if !equalValueType(p.SampleType[i], pb.SampleType[i]) {
   469				return fmt.Errorf("incompatible sample types %v and %v", p.SampleType, pb.SampleType)
   470			}
   471		}
   472		return nil
   473	}
   474	
   475	// equalValueType returns true if the two value types are semantically
   476	// equal. It ignores the internal fields used during encode/decode.
   477	func equalValueType(st1, st2 *ValueType) bool {
   478		return st1.Type == st2.Type && st1.Unit == st2.Unit
   479	}
   480	

View as plain text