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)*2)
   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  	}
   336  	key.lines = strings.Join(lines, "|")
   337  	return key
   338  }
   339  
   340  type locationKey struct {
   341  	addr, mappingID uint64
   342  	lines           string
   343  	isFolded        bool
   344  }
   345  
   346  func (pm *profileMerger) mapMapping(src *Mapping) mapInfo {
   347  	if src == nil {
   348  		return mapInfo{}
   349  	}
   350  
   351  	if mi, ok := pm.mappingsByID[src.ID]; ok {
   352  		return mi
   353  	}
   354  
   355  	// Check memoization tables.
   356  	mk := src.key()
   357  	if m, ok := pm.mappings[mk]; ok {
   358  		mi := mapInfo{m, int64(m.Start) - int64(src.Start)}
   359  		pm.mappingsByID[src.ID] = mi
   360  		return mi
   361  	}
   362  	m := &Mapping{
   363  		ID:                     uint64(len(pm.p.Mapping) + 1),
   364  		Start:                  src.Start,
   365  		Limit:                  src.Limit,
   366  		Offset:                 src.Offset,
   367  		File:                   src.File,
   368  		KernelRelocationSymbol: src.KernelRelocationSymbol,
   369  		BuildID:                src.BuildID,
   370  		HasFunctions:           src.HasFunctions,
   371  		HasFilenames:           src.HasFilenames,
   372  		HasLineNumbers:         src.HasLineNumbers,
   373  		HasInlineFrames:        src.HasInlineFrames,
   374  	}
   375  	pm.p.Mapping = append(pm.p.Mapping, m)
   376  
   377  	// Update memoization tables.
   378  	pm.mappings[mk] = m
   379  	mi := mapInfo{m, 0}
   380  	pm.mappingsByID[src.ID] = mi
   381  	return mi
   382  }
   383  
   384  // key generates encoded strings of Mapping to be used as a key for
   385  // maps.
   386  func (m *Mapping) key() mappingKey {
   387  	// Normalize addresses to handle address space randomization.
   388  	// Round up to next 4K boundary to avoid minor discrepancies.
   389  	const mapsizeRounding = 0x1000
   390  
   391  	size := m.Limit - m.Start
   392  	size = size + mapsizeRounding - 1
   393  	size = size - (size % mapsizeRounding)
   394  	key := mappingKey{
   395  		size:   size,
   396  		offset: m.Offset,
   397  	}
   398  
   399  	switch {
   400  	case m.BuildID != "":
   401  		key.buildIDOrFile = m.BuildID
   402  	case m.File != "":
   403  		key.buildIDOrFile = m.File
   404  	default:
   405  		// A mapping containing neither build ID nor file name is a fake mapping. A
   406  		// key with empty buildIDOrFile is used for fake mappings so that they are
   407  		// treated as the same mapping during merging.
   408  	}
   409  	return key
   410  }
   411  
   412  type mappingKey struct {
   413  	size, offset  uint64
   414  	buildIDOrFile string
   415  }
   416  
   417  func (pm *profileMerger) mapLine(src Line) Line {
   418  	ln := Line{
   419  		Function: pm.mapFunction(src.Function),
   420  		Line:     src.Line,
   421  	}
   422  	return ln
   423  }
   424  
   425  func (pm *profileMerger) mapFunction(src *Function) *Function {
   426  	if src == nil {
   427  		return nil
   428  	}
   429  	if f, ok := pm.functionsByID[src.ID]; ok {
   430  		return f
   431  	}
   432  	k := src.key()
   433  	if f, ok := pm.functions[k]; ok {
   434  		pm.functionsByID[src.ID] = f
   435  		return f
   436  	}
   437  	f := &Function{
   438  		ID:         uint64(len(pm.p.Function) + 1),
   439  		Name:       src.Name,
   440  		SystemName: src.SystemName,
   441  		Filename:   src.Filename,
   442  		StartLine:  src.StartLine,
   443  	}
   444  	pm.functions[k] = f
   445  	pm.functionsByID[src.ID] = f
   446  	pm.p.Function = append(pm.p.Function, f)
   447  	return f
   448  }
   449  
   450  // key generates a struct to be used as a key for maps.
   451  func (f *Function) key() functionKey {
   452  	return functionKey{
   453  		f.StartLine,
   454  		f.Name,
   455  		f.SystemName,
   456  		f.Filename,
   457  	}
   458  }
   459  
   460  type functionKey struct {
   461  	startLine                  int64
   462  	name, systemName, fileName string
   463  }
   464  
   465  // combineHeaders checks that all profiles can be merged and returns
   466  // their combined profile.
   467  func combineHeaders(srcs []*Profile) (*Profile, error) {
   468  	for _, s := range srcs[1:] {
   469  		if err := srcs[0].compatible(s); err != nil {
   470  			return nil, err
   471  		}
   472  	}
   473  
   474  	var timeNanos, durationNanos, period int64
   475  	var comments []string
   476  	seenComments := map[string]bool{}
   477  	var defaultSampleType string
   478  	for _, s := range srcs {
   479  		if timeNanos == 0 || s.TimeNanos < timeNanos {
   480  			timeNanos = s.TimeNanos
   481  		}
   482  		durationNanos += s.DurationNanos
   483  		if period == 0 || period < s.Period {
   484  			period = s.Period
   485  		}
   486  		for _, c := range s.Comments {
   487  			if seen := seenComments[c]; !seen {
   488  				comments = append(comments, c)
   489  				seenComments[c] = true
   490  			}
   491  		}
   492  		if defaultSampleType == "" {
   493  			defaultSampleType = s.DefaultSampleType
   494  		}
   495  	}
   496  
   497  	p := &Profile{
   498  		SampleType: make([]*ValueType, len(srcs[0].SampleType)),
   499  
   500  		DropFrames: srcs[0].DropFrames,
   501  		KeepFrames: srcs[0].KeepFrames,
   502  
   503  		TimeNanos:     timeNanos,
   504  		DurationNanos: durationNanos,
   505  		PeriodType:    srcs[0].PeriodType,
   506  		Period:        period,
   507  
   508  		Comments:          comments,
   509  		DefaultSampleType: defaultSampleType,
   510  	}
   511  	copy(p.SampleType, srcs[0].SampleType)
   512  	return p, nil
   513  }
   514  
   515  // compatible determines if two profiles can be compared/merged.
   516  // returns nil if the profiles are compatible; otherwise an error with
   517  // details on the incompatibility.
   518  func (p *Profile) compatible(pb *Profile) error {
   519  	if !equalValueType(p.PeriodType, pb.PeriodType) {
   520  		return fmt.Errorf("incompatible period types %v and %v", p.PeriodType, pb.PeriodType)
   521  	}
   522  
   523  	if len(p.SampleType) != len(pb.SampleType) {
   524  		return fmt.Errorf("incompatible sample types %v and %v", p.SampleType, pb.SampleType)
   525  	}
   526  
   527  	for i := range p.SampleType {
   528  		if !equalValueType(p.SampleType[i], pb.SampleType[i]) {
   529  			return fmt.Errorf("incompatible sample types %v and %v", p.SampleType, pb.SampleType)
   530  		}
   531  	}
   532  	return nil
   533  }
   534  
   535  // equalValueType returns true if the two value types are semantically
   536  // equal. It ignores the internal fields used during encode/decode.
   537  func equalValueType(st1, st2 *ValueType) bool {
   538  	return st1.Type == st2.Type && st1.Unit == st2.Unit
   539  }
   540  
   541  // locationIDMap is like a map[uint64]*Location, but provides efficiency for
   542  // ids that are densely numbered, which is often the case.
   543  type locationIDMap struct {
   544  	dense  []*Location          // indexed by id for id < len(dense)
   545  	sparse map[uint64]*Location // indexed by id for id >= len(dense)
   546  }
   547  
   548  func makeLocationIDMap(n int) locationIDMap {
   549  	return locationIDMap{
   550  		dense:  make([]*Location, n),
   551  		sparse: map[uint64]*Location{},
   552  	}
   553  }
   554  
   555  func (lm locationIDMap) get(id uint64) *Location {
   556  	if id < uint64(len(lm.dense)) {
   557  		return lm.dense[int(id)]
   558  	}
   559  	return lm.sparse[id]
   560  }
   561  
   562  func (lm locationIDMap) set(id uint64, loc *Location) {
   563  	if id < uint64(len(lm.dense)) {
   564  		lm.dense[id] = loc
   565  		return
   566  	}
   567  	lm.sparse[id] = loc
   568  }
   569  
   570  // CompatibilizeSampleTypes makes profiles compatible to be compared/merged. It
   571  // keeps sample types that appear in all profiles only and drops/reorders the
   572  // sample types as necessary.
   573  //
   574  // In the case of sample types order is not the same for given profiles the
   575  // order is derived from the first profile.
   576  //
   577  // Profiles are modified in-place.
   578  //
   579  // It returns an error if the sample type's intersection is empty.
   580  func CompatibilizeSampleTypes(ps []*Profile) error {
   581  	sTypes := commonSampleTypes(ps)
   582  	if len(sTypes) == 0 {
   583  		return fmt.Errorf("profiles have empty common sample type list")
   584  	}
   585  	for _, p := range ps {
   586  		if err := compatibilizeSampleTypes(p, sTypes); err != nil {
   587  			return err
   588  		}
   589  	}
   590  	return nil
   591  }
   592  
   593  // commonSampleTypes returns sample types that appear in all profiles in the
   594  // order how they ordered in the first profile.
   595  func commonSampleTypes(ps []*Profile) []string {
   596  	if len(ps) == 0 {
   597  		return nil
   598  	}
   599  	sTypes := map[string]int{}
   600  	for _, p := range ps {
   601  		for _, st := range p.SampleType {
   602  			sTypes[st.Type]++
   603  		}
   604  	}
   605  	var res []string
   606  	for _, st := range ps[0].SampleType {
   607  		if sTypes[st.Type] == len(ps) {
   608  			res = append(res, st.Type)
   609  		}
   610  	}
   611  	return res
   612  }
   613  
   614  // compatibilizeSampleTypes drops sample types that are not present in sTypes
   615  // list and reorder them if needed.
   616  //
   617  // It sets DefaultSampleType to sType[0] if it is not in sType list.
   618  //
   619  // It assumes that all sample types from the sTypes list are present in the
   620  // given profile otherwise it returns an error.
   621  func compatibilizeSampleTypes(p *Profile, sTypes []string) error {
   622  	if len(sTypes) == 0 {
   623  		return fmt.Errorf("sample type list is empty")
   624  	}
   625  	defaultSampleType := sTypes[0]
   626  	reMap, needToModify := make([]int, len(sTypes)), false
   627  	for i, st := range sTypes {
   628  		if st == p.DefaultSampleType {
   629  			defaultSampleType = p.DefaultSampleType
   630  		}
   631  		idx := searchValueType(p.SampleType, st)
   632  		if idx < 0 {
   633  			return fmt.Errorf("%q sample type is not found in profile", st)
   634  		}
   635  		reMap[i] = idx
   636  		if idx != i {
   637  			needToModify = true
   638  		}
   639  	}
   640  	if !needToModify && len(sTypes) == len(p.SampleType) {
   641  		return nil
   642  	}
   643  	p.DefaultSampleType = defaultSampleType
   644  	oldSampleTypes := p.SampleType
   645  	p.SampleType = make([]*ValueType, len(sTypes))
   646  	for i, idx := range reMap {
   647  		p.SampleType[i] = oldSampleTypes[idx]
   648  	}
   649  	values := make([]int64, len(sTypes))
   650  	for _, s := range p.Sample {
   651  		for i, idx := range reMap {
   652  			values[i] = s.Value[idx]
   653  		}
   654  		s.Value = s.Value[:len(values)]
   655  		copy(s.Value, values)
   656  	}
   657  	return nil
   658  }
   659  
   660  func searchValueType(vts []*ValueType, s string) int {
   661  	for i, vt := range vts {
   662  		if vt.Type == s {
   663  			return i
   664  		}
   665  	}
   666  	return -1
   667  }
   668
View as plain text