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  	"encoding/binary"
    19  	"fmt"
    20  	"sort"
    21  	"strconv"
    22  	"strings"
    23  )
    24  
    25  // Compact performs garbage collection on a profile to remove any
    26  // unreferenced fields. This is useful to reduce the size of a profile
    27  // after samples or locations have been removed.
    28  func (p *Profile) Compact() *Profile {
    29  	p, _ = Merge([]*Profile{p})
    30  	return p
    31  }
    32  
    33  // Merge merges all the profiles in profs into a single Profile.
    34  // Returns a new profile independent of the input profiles. The merged
    35  // profile is compacted to eliminate unused samples, locations,
    36  // functions and mappings. Profiles must have identical profile sample
    37  // and period types or the merge will fail. profile.Period of the
    38  // resulting profile will be the maximum of all profiles, and
    39  // profile.TimeNanos will be the earliest nonzero one. Merges are
    40  // associative with the caveat of the first profile having some
    41  // specialization in how headers are combined. There may be other
    42  // subtleties now or in the future regarding associativity.
    43  func Merge(srcs []*Profile) (*Profile, error) {
    44  	if len(srcs) == 0 {
    45  		return nil, fmt.Errorf("no profiles to merge")
    46  	}
    47  	p, err := combineHeaders(srcs)
    48  	if err != nil {
    49  		return nil, err
    50  	}
    51  
    52  	pm := &profileMerger{
    53  		p:         p,
    54  		samples:   make(map[sampleKey]*Sample, len(srcs[0].Sample)),
    55  		locations: make(map[locationKey]*Location, len(srcs[0].Location)),
    56  		functions: make(map[functionKey]*Function, len(srcs[0].Function)),
    57  		mappings:  make(map[mappingKey]*Mapping, len(srcs[0].Mapping)),
    58  	}
    59  
    60  	for _, src := range srcs {
    61  		// Clear the profile-specific hash tables
    62  		pm.locationsByID = makeLocationIDMap(len(src.Location))
    63  		pm.functionsByID = make(map[uint64]*Function, len(src.Function))
    64  		pm.mappingsByID = make(map[uint64]mapInfo, len(src.Mapping))
    65  
    66  		if len(pm.mappings) == 0 && len(src.Mapping) > 0 {
    67  			// The Mapping list has the property that the first mapping
    68  			// represents the main binary. Take the first Mapping we see,
    69  			// otherwise the operations below will add mappings in an
    70  			// arbitrary order.
    71  			pm.mapMapping(src.Mapping[0])
    72  		}
    73  
    74  		for _, s := range src.Sample {
    75  			if !isZeroSample(s) {
    76  				pm.mapSample(s)
    77  			}
    78  		}
    79  	}
    80  
    81  	for _, s := range p.Sample {
    82  		if isZeroSample(s) {
    83  			// If there are any zero samples, re-merge the profile to GC
    84  			// them.
    85  			return Merge([]*Profile{p})
    86  		}
    87  	}
    88  
    89  	return p, nil
    90  }
    91  
    92  // Normalize normalizes the source profile by multiplying each value in profile by the
    93  // ratio of the sum of the base profile's values of that sample type to the sum of the
    94  // source profile's value of that sample type.
    95  func (p *Profile) Normalize(pb *Profile) error {
    96  
    97  	if err := p.compatible(pb); err != nil {
    98  		return err
    99  	}
   100  
   101  	baseVals := make([]int64, len(p.SampleType))
   102  	for _, s := range pb.Sample {
   103  		for i, v := range s.Value {
   104  			baseVals[i] += v
   105  		}
   106  	}
   107  
   108  	srcVals := make([]int64, len(p.SampleType))
   109  	for _, s := range p.Sample {
   110  		for i, v := range s.Value {
   111  			srcVals[i] += v
   112  		}
   113  	}
   114  
   115  	normScale := make([]float64, len(baseVals))
   116  	for i := range baseVals {
   117  		if srcVals[i] == 0 {
   118  			normScale[i] = 0.0
   119  		} else {
   120  			normScale[i] = float64(baseVals[i]) / float64(srcVals[i])
   121  		}
   122  	}
   123  	p.ScaleN(normScale)
   124  	return nil
   125  }
   126  
   127  func isZeroSample(s *Sample) bool {
   128  	for _, v := range s.Value {
   129  		if v != 0 {
   130  			return false
   131  		}
   132  	}
   133  	return true
   134  }
   135  
   136  type profileMerger struct {
   137  	p *Profile
   138  
   139  	// Memoization tables within a profile.
   140  	locationsByID locationIDMap
   141  	functionsByID map[uint64]*Function
   142  	mappingsByID  map[uint64]mapInfo
   143  
   144  	// Memoization tables for profile entities.
   145  	samples   map[sampleKey]*Sample
   146  	locations map[locationKey]*Location
   147  	functions map[functionKey]*Function
   148  	mappings  map[mappingKey]*Mapping
   149  }
   150  
   151  type mapInfo struct {
   152  	m      *Mapping
   153  	offset int64
   154  }
   155  
   156  func (pm *profileMerger) mapSample(src *Sample) *Sample {
   157  	// Check memoization table
   158  	k := pm.sampleKey(src)
   159  	if ss, ok := pm.samples[k]; ok {
   160  		for i, v := range src.Value {
   161  			ss.Value[i] += v
   162  		}
   163  		return ss
   164  	}
   165  
   166  	// Make new sample.
   167  	s := &Sample{
   168  		Location: make([]*Location, len(src.Location)),
   169  		Value:    make([]int64, len(src.Value)),
   170  		Label:    make(map[string][]string, len(src.Label)),
   171  		NumLabel: make(map[string][]int64, len(src.NumLabel)),
   172  		NumUnit:  make(map[string][]string, len(src.NumLabel)),
   173  	}
   174  	for i, l := range src.Location {
   175  		s.Location[i] = pm.mapLocation(l)
   176  	}
   177  	for k, v := range src.Label {
   178  		vv := make([]string, len(v))
   179  		copy(vv, v)
   180  		s.Label[k] = vv
   181  	}
   182  	for k, v := range src.NumLabel {
   183  		u := src.NumUnit[k]
   184  		vv := make([]int64, len(v))
   185  		uu := make([]string, len(u))
   186  		copy(vv, v)
   187  		copy(uu, u)
   188  		s.NumLabel[k] = vv
   189  		s.NumUnit[k] = uu
   190  	}
   191  	copy(s.Value, src.Value)
   192  	pm.samples[k] = s
   193  	pm.p.Sample = append(pm.p.Sample, s)
   194  	return s
   195  }
   196  
   197  func (pm *profileMerger) sampleKey(sample *Sample) sampleKey {
   198  	// Accumulate contents into a string.
   199  	var buf strings.Builder
   200  	buf.Grow(64) // Heuristic to avoid extra allocs
   201  
   202  	// encode a number
   203  	putNumber := func(v uint64) {
   204  		var num [binary.MaxVarintLen64]byte
   205  		n := binary.PutUvarint(num[:], v)
   206  		buf.Write(num[:n])
   207  	}
   208  
   209  	// encode a string prefixed with its length.
   210  	putDelimitedString := func(s string) {
   211  		putNumber(uint64(len(s)))
   212  		buf.WriteString(s)
   213  	}
   214  
   215  	for _, l := range sample.Location {
   216  		// Get the location in the merged profile, which may have a different ID.
   217  		if loc := pm.mapLocation(l); loc != nil {
   218  			putNumber(loc.ID)
   219  		}
   220  	}
   221  	putNumber(0) // Delimiter
   222  
   223  	for _, l := range sortedKeys1(sample.Label) {
   224  		putDelimitedString(l)
   225  		values := sample.Label[l]
   226  		putNumber(uint64(len(values)))
   227  		for _, v := range values {
   228  			putDelimitedString(v)
   229  		}
   230  	}
   231  
   232  	for _, l := range sortedKeys2(sample.NumLabel) {
   233  		putDelimitedString(l)
   234  		values := sample.NumLabel[l]
   235  		putNumber(uint64(len(values)))
   236  		for _, v := range values {
   237  			putNumber(uint64(v))
   238  		}
   239  		units := sample.NumUnit[l]
   240  		putNumber(uint64(len(units)))
   241  		for _, v := range units {
   242  			putDelimitedString(v)
   243  		}
   244  	}
   245  
   246  	return sampleKey(buf.String())
   247  }
   248  
   249  type sampleKey string
   250  
   251  // sortedKeys1 returns the sorted keys found in a string->[]string map.
   252  //
   253  // Note: this is currently non-generic since github pprof runs golint,
   254  // which does not support generics. When that issue is fixed, it can
   255  // be merged with sortedKeys2 and made into a generic function.
   256  func sortedKeys1(m map[string][]string) []string {
   257  	if len(m) == 0 {
   258  		return nil
   259  	}
   260  	keys := make([]string, 0, len(m))
   261  	for k := range m {
   262  		keys = append(keys, k)
   263  	}
   264  	sort.Strings(keys)
   265  	return keys
   266  }
   267  
   268  // sortedKeys2 returns the sorted keys found in a string->[]int64 map.
   269  //
   270  // Note: this is currently non-generic since github pprof runs golint,
   271  // which does not support generics. When that issue is fixed, it can
   272  // be merged with sortedKeys1 and made into a generic function.
   273  func sortedKeys2(m map[string][]int64) []string {
   274  	if len(m) == 0 {
   275  		return nil
   276  	}
   277  	keys := make([]string, 0, len(m))
   278  	for k := range m {
   279  		keys = append(keys, k)
   280  	}
   281  	sort.Strings(keys)
   282  	return keys
   283  }
   284  
   285  func (pm *profileMerger) mapLocation(src *Location) *Location {
   286  	if src == nil {
   287  		return nil
   288  	}
   289  
   290  	if l := pm.locationsByID.get(src.ID); l != nil {
   291  		return l
   292  	}
   293  
   294  	mi := pm.mapMapping(src.Mapping)
   295  	l := &Location{
   296  		ID:       uint64(len(pm.p.Location) + 1),
   297  		Mapping:  mi.m,
   298  		Address:  uint64(int64(src.Address) + mi.offset),
   299  		Line:     make([]Line, len(src.Line)),
   300  		IsFolded: src.IsFolded,
   301  	}
   302  	for i, ln := range src.Line {
   303  		l.Line[i] = pm.mapLine(ln)
   304  	}
   305  	// Check memoization table. Must be done on the remapped location to
   306  	// account for the remapped mapping ID.
   307  	k := l.key()
   308  	if ll, ok := pm.locations[k]; ok {
   309  		pm.locationsByID.set(src.ID, ll)
   310  		return ll
   311  	}
   312  	pm.locationsByID.set(src.ID, l)
   313  	pm.locations[k] = l
   314  	pm.p.Location = append(pm.p.Location, l)
   315  	return l
   316  }
   317  
   318  // key generates locationKey to be used as a key for maps.
   319  func (l *Location) key() locationKey {
   320  	key := locationKey{
   321  		addr:     l.Address,
   322  		isFolded: l.IsFolded,
   323  	}
   324  	if l.Mapping != nil {
   325  		// Normalizes address to handle address space randomization.
   326  		key.addr -= l.Mapping.Start
   327  		key.mappingID = l.Mapping.ID
   328  	}
   329  	lines := make([]string, len(l.Line)*3)
   330  	for i, line := range l.Line {
   331  		if line.Function != nil {
   332  			lines[i*2] = strconv.FormatUint(line.Function.ID, 16)
   333  		}
   334  		lines[i*2+1] = strconv.FormatInt(line.Line, 16)
   335  		lines[i*2+2] = strconv.FormatInt(line.Column, 16)
   336  	}
   337  	key.lines = strings.Join(lines, "|")
   338  	return key
   339  }
   340  
   341  type locationKey struct {
   342  	addr, mappingID uint64
   343  	lines           string
   344  	isFolded        bool
   345  }
   346  
   347  func (pm *profileMerger) mapMapping(src *Mapping) mapInfo {
   348  	if src == nil {
   349  		return mapInfo{}
   350  	}
   351  
   352  	if mi, ok := pm.mappingsByID[src.ID]; ok {
   353  		return mi
   354  	}
   355  
   356  	// Check memoization tables.
   357  	mk := src.key()
   358  	if m, ok := pm.mappings[mk]; ok {
   359  		mi := mapInfo{m, int64(m.Start) - int64(src.Start)}
   360  		pm.mappingsByID[src.ID] = mi
   361  		return mi
   362  	}
   363  	m := &Mapping{
   364  		ID:                     uint64(len(pm.p.Mapping) + 1),
   365  		Start:                  src.Start,
   366  		Limit:                  src.Limit,
   367  		Offset:                 src.Offset,
   368  		File:                   src.File,
   369  		KernelRelocationSymbol: src.KernelRelocationSymbol,
   370  		BuildID:                src.BuildID,
   371  		HasFunctions:           src.HasFunctions,
   372  		HasFilenames:           src.HasFilenames,
   373  		HasLineNumbers:         src.HasLineNumbers,
   374  		HasInlineFrames:        src.HasInlineFrames,
   375  	}
   376  	pm.p.Mapping = append(pm.p.Mapping, m)
   377  
   378  	// Update memoization tables.
   379  	pm.mappings[mk] = m
   380  	mi := mapInfo{m, 0}
   381  	pm.mappingsByID[src.ID] = mi
   382  	return mi
   383  }
   384  
   385  // key generates encoded strings of Mapping to be used as a key for
   386  // maps.
   387  func (m *Mapping) key() mappingKey {
   388  	// Normalize addresses to handle address space randomization.
   389  	// Round up to next 4K boundary to avoid minor discrepancies.
   390  	const mapsizeRounding = 0x1000
   391  
   392  	size := m.Limit - m.Start
   393  	size = size + mapsizeRounding - 1
   394  	size = size - (size % mapsizeRounding)
   395  	key := mappingKey{
   396  		size:   size,
   397  		offset: m.Offset,
   398  	}
   399  
   400  	switch {
   401  	case m.BuildID != "":
   402  		key.buildIDOrFile = m.BuildID
   403  	case m.File != "":
   404  		key.buildIDOrFile = m.File
   405  	default:
   406  		// A mapping containing neither build ID nor file name is a fake mapping. A
   407  		// key with empty buildIDOrFile is used for fake mappings so that they are
   408  		// treated as the same mapping during merging.
   409  	}
   410  	return key
   411  }
   412  
   413  type mappingKey struct {
   414  	size, offset  uint64
   415  	buildIDOrFile string
   416  }
   417  
   418  func (pm *profileMerger) mapLine(src Line) Line {
   419  	ln := Line{
   420  		Function: pm.mapFunction(src.Function),
   421  		Line:     src.Line,
   422  		Column:   src.Column,
   423  	}
   424  	return ln
   425  }
   426  
   427  func (pm *profileMerger) mapFunction(src *Function) *Function {
   428  	if src == nil {
   429  		return nil
   430  	}
   431  	if f, ok := pm.functionsByID[src.ID]; ok {
   432  		return f
   433  	}
   434  	k := src.key()
   435  	if f, ok := pm.functions[k]; ok {
   436  		pm.functionsByID[src.ID] = f
   437  		return f
   438  	}
   439  	f := &Function{
   440  		ID:         uint64(len(pm.p.Function) + 1),
   441  		Name:       src.Name,
   442  		SystemName: src.SystemName,
   443  		Filename:   src.Filename,
   444  		StartLine:  src.StartLine,
   445  	}
   446  	pm.functions[k] = f
   447  	pm.functionsByID[src.ID] = f
   448  	pm.p.Function = append(pm.p.Function, f)
   449  	return f
   450  }
   451  
   452  // key generates a struct to be used as a key for maps.
   453  func (f *Function) key() functionKey {
   454  	return functionKey{
   455  		f.StartLine,
   456  		f.Name,
   457  		f.SystemName,
   458  		f.Filename,
   459  	}
   460  }
   461  
   462  type functionKey struct {
   463  	startLine                  int64
   464  	name, systemName, fileName string
   465  }
   466  
   467  // combineHeaders checks that all profiles can be merged and returns
   468  // their combined profile.
   469  func combineHeaders(srcs []*Profile) (*Profile, error) {
   470  	for _, s := range srcs[1:] {
   471  		if err := srcs[0].compatible(s); err != nil {
   472  			return nil, err
   473  		}
   474  	}
   475  
   476  	var timeNanos, durationNanos, period int64
   477  	var comments []string
   478  	seenComments := map[string]bool{}
   479  	var docURL string
   480  	var defaultSampleType string
   481  	for _, s := range srcs {
   482  		if timeNanos == 0 || s.TimeNanos < timeNanos {
   483  			timeNanos = s.TimeNanos
   484  		}
   485  		durationNanos += s.DurationNanos
   486  		if period == 0 || period < s.Period {
   487  			period = s.Period
   488  		}
   489  		for _, c := range s.Comments {
   490  			if seen := seenComments[c]; !seen {
   491  				comments = append(comments, c)
   492  				seenComments[c] = true
   493  			}
   494  		}
   495  		if defaultSampleType == "" {
   496  			defaultSampleType = s.DefaultSampleType
   497  		}
   498  		if docURL == "" {
   499  			docURL = s.DocURL
   500  		}
   501  	}
   502  
   503  	p := &Profile{
   504  		SampleType: make([]*ValueType, len(srcs[0].SampleType)),
   505  
   506  		DropFrames: srcs[0].DropFrames,
   507  		KeepFrames: srcs[0].KeepFrames,
   508  
   509  		TimeNanos:     timeNanos,
   510  		DurationNanos: durationNanos,
   511  		PeriodType:    srcs[0].PeriodType,
   512  		Period:        period,
   513  
   514  		Comments:          comments,
   515  		DefaultSampleType: defaultSampleType,
   516  		DocURL:            docURL,
   517  	}
   518  	copy(p.SampleType, srcs[0].SampleType)
   519  	return p, nil
   520  }
   521  
   522  // compatible determines if two profiles can be compared/merged.
   523  // returns nil if the profiles are compatible; otherwise an error with
   524  // details on the incompatibility.
   525  func (p *Profile) compatible(pb *Profile) error {
   526  	if !equalValueType(p.PeriodType, pb.PeriodType) {
   527  		return fmt.Errorf("incompatible period types %v and %v", p.PeriodType, pb.PeriodType)
   528  	}
   529  
   530  	if len(p.SampleType) != len(pb.SampleType) {
   531  		return fmt.Errorf("incompatible sample types %v and %v", p.SampleType, pb.SampleType)
   532  	}
   533  
   534  	for i := range p.SampleType {
   535  		if !equalValueType(p.SampleType[i], pb.SampleType[i]) {
   536  			return fmt.Errorf("incompatible sample types %v and %v", p.SampleType, pb.SampleType)
   537  		}
   538  	}
   539  	return nil
   540  }
   541  
   542  // equalValueType returns true if the two value types are semantically
   543  // equal. It ignores the internal fields used during encode/decode.
   544  func equalValueType(st1, st2 *ValueType) bool {
   545  	return st1.Type == st2.Type && st1.Unit == st2.Unit
   546  }
   547  
   548  // locationIDMap is like a map[uint64]*Location, but provides efficiency for
   549  // ids that are densely numbered, which is often the case.
   550  type locationIDMap struct {
   551  	dense  []*Location          // indexed by id for id < len(dense)
   552  	sparse map[uint64]*Location // indexed by id for id >= len(dense)
   553  }
   554  
   555  func makeLocationIDMap(n int) locationIDMap {
   556  	return locationIDMap{
   557  		dense:  make([]*Location, n),
   558  		sparse: map[uint64]*Location{},
   559  	}
   560  }
   561  
   562  func (lm locationIDMap) get(id uint64) *Location {
   563  	if id < uint64(len(lm.dense)) {
   564  		return lm.dense[int(id)]
   565  	}
   566  	return lm.sparse[id]
   567  }
   568  
   569  func (lm locationIDMap) set(id uint64, loc *Location) {
   570  	if id < uint64(len(lm.dense)) {
   571  		lm.dense[id] = loc
   572  		return
   573  	}
   574  	lm.sparse[id] = loc
   575  }
   576  
   577  // CompatibilizeSampleTypes makes profiles compatible to be compared/merged. It
   578  // keeps sample types that appear in all profiles only and drops/reorders the
   579  // sample types as necessary.
   580  //
   581  // In the case of sample types order is not the same for given profiles the
   582  // order is derived from the first profile.
   583  //
   584  // Profiles are modified in-place.
   585  //
   586  // It returns an error if the sample type's intersection is empty.
   587  func CompatibilizeSampleTypes(ps []*Profile) error {
   588  	sTypes := commonSampleTypes(ps)
   589  	if len(sTypes) == 0 {
   590  		return fmt.Errorf("profiles have empty common sample type list")
   591  	}
   592  	for _, p := range ps {
   593  		if err := compatibilizeSampleTypes(p, sTypes); err != nil {
   594  			return err
   595  		}
   596  	}
   597  	return nil
   598  }
   599  
   600  // commonSampleTypes returns sample types that appear in all profiles in the
   601  // order how they ordered in the first profile.
   602  func commonSampleTypes(ps []*Profile) []string {
   603  	if len(ps) == 0 {
   604  		return nil
   605  	}
   606  	sTypes := map[string]int{}
   607  	for _, p := range ps {
   608  		for _, st := range p.SampleType {
   609  			sTypes[st.Type]++
   610  		}
   611  	}
   612  	var res []string
   613  	for _, st := range ps[0].SampleType {
   614  		if sTypes[st.Type] == len(ps) {
   615  			res = append(res, st.Type)
   616  		}
   617  	}
   618  	return res
   619  }
   620  
   621  // compatibilizeSampleTypes drops sample types that are not present in sTypes
   622  // list and reorder them if needed.
   623  //
   624  // It sets DefaultSampleType to sType[0] if it is not in sType list.
   625  //
   626  // It assumes that all sample types from the sTypes list are present in the
   627  // given profile otherwise it returns an error.
   628  func compatibilizeSampleTypes(p *Profile, sTypes []string) error {
   629  	if len(sTypes) == 0 {
   630  		return fmt.Errorf("sample type list is empty")
   631  	}
   632  	defaultSampleType := sTypes[0]
   633  	reMap, needToModify := make([]int, len(sTypes)), false
   634  	for i, st := range sTypes {
   635  		if st == p.DefaultSampleType {
   636  			defaultSampleType = p.DefaultSampleType
   637  		}
   638  		idx := searchValueType(p.SampleType, st)
   639  		if idx < 0 {
   640  			return fmt.Errorf("%q sample type is not found in profile", st)
   641  		}
   642  		reMap[i] = idx
   643  		if idx != i {
   644  			needToModify = true
   645  		}
   646  	}
   647  	if !needToModify && len(sTypes) == len(p.SampleType) {
   648  		return nil
   649  	}
   650  	p.DefaultSampleType = defaultSampleType
   651  	oldSampleTypes := p.SampleType
   652  	p.SampleType = make([]*ValueType, len(sTypes))
   653  	for i, idx := range reMap {
   654  		p.SampleType[i] = oldSampleTypes[idx]
   655  	}
   656  	values := make([]int64, len(sTypes))
   657  	for _, s := range p.Sample {
   658  		for i, idx := range reMap {
   659  			values[i] = s.Value[idx]
   660  		}
   661  		s.Value = s.Value[:len(values)]
   662  		copy(s.Value, values)
   663  	}
   664  	return nil
   665  }
   666  
   667  func searchValueType(vts []*ValueType, s string) int {
   668  	for i, vt := range vts {
   669  		if vt.Type == s {
   670  			return i
   671  		}
   672  	}
   673  	return -1
   674  }
   675
View as plain text