podman

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. Merges are
39
// associative with the caveat of the first profile having some
40
// specialization in how headers are combined. There may be other
41
// subtleties now or in the future regarding associativity.
42
func Merge(srcs []*Profile) (*Profile, error) {
43
	if len(srcs) == 0 {
44
		return nil, fmt.Errorf("no profiles to merge")
45
	}
46
	p, err := combineHeaders(srcs)
47
	if err != nil {
48
		return nil, err
49
	}
50

51
	pm := &profileMerger{
52
		p:         p,
53
		samples:   make(map[sampleKey]*Sample, len(srcs[0].Sample)),
54
		locations: make(map[locationKey]*Location, len(srcs[0].Location)),
55
		functions: make(map[functionKey]*Function, len(srcs[0].Function)),
56
		mappings:  make(map[mappingKey]*Mapping, len(srcs[0].Mapping)),
57
	}
58

59
	for _, src := range srcs {
60
		// Clear the profile-specific hash tables
61
		pm.locationsByID = make(map[uint64]*Location, len(src.Location))
62
		pm.functionsByID = make(map[uint64]*Function, len(src.Function))
63
		pm.mappingsByID = make(map[uint64]mapInfo, len(src.Mapping))
64

65
		if len(pm.mappings) == 0 && len(src.Mapping) > 0 {
66
			// The Mapping list has the property that the first mapping
67
			// represents the main binary. Take the first Mapping we see,
68
			// otherwise the operations below will add mappings in an
69
			// arbitrary order.
70
			pm.mapMapping(src.Mapping[0])
71
		}
72

73
		for _, s := range src.Sample {
74
			if !isZeroSample(s) {
75
				pm.mapSample(s)
76
			}
77
		}
78
	}
79

80
	for _, s := range p.Sample {
81
		if isZeroSample(s) {
82
			// If there are any zero samples, re-merge the profile to GC
83
			// them.
84
			return Merge([]*Profile{p})
85
		}
86
	}
87

88
	return p, nil
89
}
90

91
// Normalize normalizes the source profile by multiplying each value in profile by the
92
// ratio of the sum of the base profile's values of that sample type to the sum of the
93
// source profile's value of that sample type.
94
func (p *Profile) Normalize(pb *Profile) error {
95

96
	if err := p.compatible(pb); err != nil {
97
		return err
98
	}
99

100
	baseVals := make([]int64, len(p.SampleType))
101
	for _, s := range pb.Sample {
102
		for i, v := range s.Value {
103
			baseVals[i] += v
104
		}
105
	}
106

107
	srcVals := make([]int64, len(p.SampleType))
108
	for _, s := range p.Sample {
109
		for i, v := range s.Value {
110
			srcVals[i] += v
111
		}
112
	}
113

114
	normScale := make([]float64, len(baseVals))
115
	for i := range baseVals {
116
		if srcVals[i] == 0 {
117
			normScale[i] = 0.0
118
		} else {
119
			normScale[i] = float64(baseVals[i]) / float64(srcVals[i])
120
		}
121
	}
122
	p.ScaleN(normScale)
123
	return nil
124
}
125

126
func isZeroSample(s *Sample) bool {
127
	for _, v := range s.Value {
128
		if v != 0 {
129
			return false
130
		}
131
	}
132
	return true
133
}
134

135
type profileMerger struct {
136
	p *Profile
137

138
	// Memoization tables within a profile.
139
	locationsByID map[uint64]*Location
140
	functionsByID map[uint64]*Function
141
	mappingsByID  map[uint64]mapInfo
142

143
	// Memoization tables for profile entities.
144
	samples   map[sampleKey]*Sample
145
	locations map[locationKey]*Location
146
	functions map[functionKey]*Function
147
	mappings  map[mappingKey]*Mapping
148
}
149

150
type mapInfo struct {
151
	m      *Mapping
152
	offset int64
153
}
154

155
func (pm *profileMerger) mapSample(src *Sample) *Sample {
156
	s := &Sample{
157
		Location: make([]*Location, len(src.Location)),
158
		Value:    make([]int64, len(src.Value)),
159
		Label:    make(map[string][]string, len(src.Label)),
160
		NumLabel: make(map[string][]int64, len(src.NumLabel)),
161
		NumUnit:  make(map[string][]string, len(src.NumLabel)),
162
	}
163
	for i, l := range src.Location {
164
		s.Location[i] = pm.mapLocation(l)
165
	}
166
	for k, v := range src.Label {
167
		vv := make([]string, len(v))
168
		copy(vv, v)
169
		s.Label[k] = vv
170
	}
171
	for k, v := range src.NumLabel {
172
		u := src.NumUnit[k]
173
		vv := make([]int64, len(v))
174
		uu := make([]string, len(u))
175
		copy(vv, v)
176
		copy(uu, u)
177
		s.NumLabel[k] = vv
178
		s.NumUnit[k] = uu
179
	}
180
	// Check memoization table. Must be done on the remapped location to
181
	// account for the remapped mapping. Add current values to the
182
	// existing sample.
183
	k := s.key()
184
	if ss, ok := pm.samples[k]; ok {
185
		for i, v := range src.Value {
186
			ss.Value[i] += v
187
		}
188
		return ss
189
	}
190
	copy(s.Value, src.Value)
191
	pm.samples[k] = s
192
	pm.p.Sample = append(pm.p.Sample, s)
193
	return s
194
}
195

196
// key generates sampleKey to be used as a key for maps.
197
func (sample *Sample) key() sampleKey {
198
	ids := make([]string, len(sample.Location))
199
	for i, l := range sample.Location {
200
		ids[i] = strconv.FormatUint(l.ID, 16)
201
	}
202

203
	labels := make([]string, 0, len(sample.Label))
204
	for k, v := range sample.Label {
205
		labels = append(labels, fmt.Sprintf("%q%q", k, v))
206
	}
207
	sort.Strings(labels)
208

209
	numlabels := make([]string, 0, len(sample.NumLabel))
210
	for k, v := range sample.NumLabel {
211
		numlabels = append(numlabels, fmt.Sprintf("%q%x%x", k, v, sample.NumUnit[k]))
212
	}
213
	sort.Strings(numlabels)
214

215
	return sampleKey{
216
		strings.Join(ids, "|"),
217
		strings.Join(labels, ""),
218
		strings.Join(numlabels, ""),
219
	}
220
}
221

222
type sampleKey struct {
223
	locations string
224
	labels    string
225
	numlabels string
226
}
227

228
func (pm *profileMerger) mapLocation(src *Location) *Location {
229
	if src == nil {
230
		return nil
231
	}
232

233
	if l, ok := pm.locationsByID[src.ID]; ok {
234
		return l
235
	}
236

237
	mi := pm.mapMapping(src.Mapping)
238
	l := &Location{
239
		ID:       uint64(len(pm.p.Location) + 1),
240
		Mapping:  mi.m,
241
		Address:  uint64(int64(src.Address) + mi.offset),
242
		Line:     make([]Line, len(src.Line)),
243
		IsFolded: src.IsFolded,
244
	}
245
	for i, ln := range src.Line {
246
		l.Line[i] = pm.mapLine(ln)
247
	}
248
	// Check memoization table. Must be done on the remapped location to
249
	// account for the remapped mapping ID.
250
	k := l.key()
251
	if ll, ok := pm.locations[k]; ok {
252
		pm.locationsByID[src.ID] = ll
253
		return ll
254
	}
255
	pm.locationsByID[src.ID] = l
256
	pm.locations[k] = l
257
	pm.p.Location = append(pm.p.Location, l)
258
	return l
259
}
260

261
// key generates locationKey to be used as a key for maps.
262
func (l *Location) key() locationKey {
263
	key := locationKey{
264
		addr:     l.Address,
265
		isFolded: l.IsFolded,
266
	}
267
	if l.Mapping != nil {
268
		// Normalizes address to handle address space randomization.
269
		key.addr -= l.Mapping.Start
270
		key.mappingID = l.Mapping.ID
271
	}
272
	lines := make([]string, len(l.Line)*2)
273
	for i, line := range l.Line {
274
		if line.Function != nil {
275
			lines[i*2] = strconv.FormatUint(line.Function.ID, 16)
276
		}
277
		lines[i*2+1] = strconv.FormatInt(line.Line, 16)
278
	}
279
	key.lines = strings.Join(lines, "|")
280
	return key
281
}
282

283
type locationKey struct {
284
	addr, mappingID uint64
285
	lines           string
286
	isFolded        bool
287
}
288

289
func (pm *profileMerger) mapMapping(src *Mapping) mapInfo {
290
	if src == nil {
291
		return mapInfo{}
292
	}
293

294
	if mi, ok := pm.mappingsByID[src.ID]; ok {
295
		return mi
296
	}
297

298
	// Check memoization tables.
299
	mk := src.key()
300
	if m, ok := pm.mappings[mk]; ok {
301
		mi := mapInfo{m, int64(m.Start) - int64(src.Start)}
302
		pm.mappingsByID[src.ID] = mi
303
		return mi
304
	}
305
	m := &Mapping{
306
		ID:              uint64(len(pm.p.Mapping) + 1),
307
		Start:           src.Start,
308
		Limit:           src.Limit,
309
		Offset:          src.Offset,
310
		File:            src.File,
311
		BuildID:         src.BuildID,
312
		HasFunctions:    src.HasFunctions,
313
		HasFilenames:    src.HasFilenames,
314
		HasLineNumbers:  src.HasLineNumbers,
315
		HasInlineFrames: src.HasInlineFrames,
316
	}
317
	pm.p.Mapping = append(pm.p.Mapping, m)
318

319
	// Update memoization tables.
320
	pm.mappings[mk] = m
321
	mi := mapInfo{m, 0}
322
	pm.mappingsByID[src.ID] = mi
323
	return mi
324
}
325

326
// key generates encoded strings of Mapping to be used as a key for
327
// maps.
328
func (m *Mapping) key() mappingKey {
329
	// Normalize addresses to handle address space randomization.
330
	// Round up to next 4K boundary to avoid minor discrepancies.
331
	const mapsizeRounding = 0x1000
332

333
	size := m.Limit - m.Start
334
	size = size + mapsizeRounding - 1
335
	size = size - (size % mapsizeRounding)
336
	key := mappingKey{
337
		size:   size,
338
		offset: m.Offset,
339
	}
340

341
	switch {
342
	case m.BuildID != "":
343
		key.buildIDOrFile = m.BuildID
344
	case m.File != "":
345
		key.buildIDOrFile = m.File
346
	default:
347
		// A mapping containing neither build ID nor file name is a fake mapping. A
348
		// key with empty buildIDOrFile is used for fake mappings so that they are
349
		// treated as the same mapping during merging.
350
	}
351
	return key
352
}
353

354
type mappingKey struct {
355
	size, offset  uint64
356
	buildIDOrFile string
357
}
358

359
func (pm *profileMerger) mapLine(src Line) Line {
360
	ln := Line{
361
		Function: pm.mapFunction(src.Function),
362
		Line:     src.Line,
363
	}
364
	return ln
365
}
366

367
func (pm *profileMerger) mapFunction(src *Function) *Function {
368
	if src == nil {
369
		return nil
370
	}
371
	if f, ok := pm.functionsByID[src.ID]; ok {
372
		return f
373
	}
374
	k := src.key()
375
	if f, ok := pm.functions[k]; ok {
376
		pm.functionsByID[src.ID] = f
377
		return f
378
	}
379
	f := &Function{
380
		ID:         uint64(len(pm.p.Function) + 1),
381
		Name:       src.Name,
382
		SystemName: src.SystemName,
383
		Filename:   src.Filename,
384
		StartLine:  src.StartLine,
385
	}
386
	pm.functions[k] = f
387
	pm.functionsByID[src.ID] = f
388
	pm.p.Function = append(pm.p.Function, f)
389
	return f
390
}
391

392
// key generates a struct to be used as a key for maps.
393
func (f *Function) key() functionKey {
394
	return functionKey{
395
		f.StartLine,
396
		f.Name,
397
		f.SystemName,
398
		f.Filename,
399
	}
400
}
401

402
type functionKey struct {
403
	startLine                  int64
404
	name, systemName, fileName string
405
}
406

407
// combineHeaders checks that all profiles can be merged and returns
408
// their combined profile.
409
func combineHeaders(srcs []*Profile) (*Profile, error) {
410
	for _, s := range srcs[1:] {
411
		if err := srcs[0].compatible(s); err != nil {
412
			return nil, err
413
		}
414
	}
415

416
	var timeNanos, durationNanos, period int64
417
	var comments []string
418
	seenComments := map[string]bool{}
419
	var defaultSampleType string
420
	for _, s := range srcs {
421
		if timeNanos == 0 || s.TimeNanos < timeNanos {
422
			timeNanos = s.TimeNanos
423
		}
424
		durationNanos += s.DurationNanos
425
		if period == 0 || period < s.Period {
426
			period = s.Period
427
		}
428
		for _, c := range s.Comments {
429
			if seen := seenComments[c]; !seen {
430
				comments = append(comments, c)
431
				seenComments[c] = true
432
			}
433
		}
434
		if defaultSampleType == "" {
435
			defaultSampleType = s.DefaultSampleType
436
		}
437
	}
438

439
	p := &Profile{
440
		SampleType: make([]*ValueType, len(srcs[0].SampleType)),
441

442
		DropFrames: srcs[0].DropFrames,
443
		KeepFrames: srcs[0].KeepFrames,
444

445
		TimeNanos:     timeNanos,
446
		DurationNanos: durationNanos,
447
		PeriodType:    srcs[0].PeriodType,
448
		Period:        period,
449

450
		Comments:          comments,
451
		DefaultSampleType: defaultSampleType,
452
	}
453
	copy(p.SampleType, srcs[0].SampleType)
454
	return p, nil
455
}
456

457
// compatible determines if two profiles can be compared/merged.
458
// returns nil if the profiles are compatible; otherwise an error with
459
// details on the incompatibility.
460
func (p *Profile) compatible(pb *Profile) error {
461
	if !equalValueType(p.PeriodType, pb.PeriodType) {
462
		return fmt.Errorf("incompatible period types %v and %v", p.PeriodType, pb.PeriodType)
463
	}
464

465
	if len(p.SampleType) != len(pb.SampleType) {
466
		return fmt.Errorf("incompatible sample types %v and %v", p.SampleType, pb.SampleType)
467
	}
468

469
	for i := range p.SampleType {
470
		if !equalValueType(p.SampleType[i], pb.SampleType[i]) {
471
			return fmt.Errorf("incompatible sample types %v and %v", p.SampleType, pb.SampleType)
472
		}
473
	}
474
	return nil
475
}
476

477
// equalValueType returns true if the two value types are semantically
478
// equal. It ignores the internal fields used during encode/decode.
479
func equalValueType(st1, st2 *ValueType) bool {
480
	return st1.Type == st2.Type && st1.Unit == st2.Unit
481
}
482