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(srcs[0].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 } 242 for i, ln := range src.Line { 243 l.Line[i] = pm.mapLine(ln) 244 } 245 // Check memoization table. Must be done on the remapped location to 246 // account for the remapped mapping ID. 247 k := l.key() 248 if ll, ok := pm.locations[k]; ok { 249 pm.locationsByID[src.ID] = ll 250 return ll 251 } 252 pm.locationsByID[src.ID] = l 253 pm.locations[k] = l 254 pm.p.Location = append(pm.p.Location, l) 255 return l 256 } 257 258 // key generates locationKey to be used as a key for maps. 259 func (l *Location) key() locationKey { 260 key := locationKey{ 261 addr: l.Address, 262 } 263 if l.Mapping != nil { 264 // Normalizes address to handle address space randomization. 265 key.addr -= l.Mapping.Start 266 key.mappingID = l.Mapping.ID 267 } 268 lines := make([]string, len(l.Line)*2) 269 for i, line := range l.Line { 270 if line.Function != nil { 271 lines[i*2] = strconv.FormatUint(line.Function.ID, 16) 272 } 273 lines[i*2+1] = strconv.FormatInt(line.Line, 16) 274 } 275 key.lines = strings.Join(lines, "|") 276 return key 277 } 278 279 type locationKey struct { 280 addr, mappingID uint64 281 lines string 282 } 283 284 func (pm *profileMerger) mapMapping(src *Mapping) mapInfo { 285 if src == nil { 286 return mapInfo{} 287 } 288 289 if mi, ok := pm.mappingsByID[src.ID]; ok { 290 return mi 291 } 292 293 // Check memoization tables. 294 bk, pk := src.key() 295 if src.BuildID != "" { 296 if m, ok := pm.mappings[bk]; ok { 297 mi := mapInfo{m, int64(m.Start) - int64(src.Start)} 298 pm.mappingsByID[src.ID] = mi 299 return mi 300 } 301 } 302 if src.File != "" { 303 if m, ok := pm.mappings[pk]; ok { 304 mi := mapInfo{m, int64(m.Start) - int64(src.Start)} 305 pm.mappingsByID[src.ID] = mi 306 return mi 307 } 308 } 309 m := &Mapping{ 310 ID: uint64(len(pm.p.Mapping) + 1), 311 Start: src.Start, 312 Limit: src.Limit, 313 Offset: src.Offset, 314 File: src.File, 315 BuildID: src.BuildID, 316 HasFunctions: src.HasFunctions, 317 HasFilenames: src.HasFilenames, 318 HasLineNumbers: src.HasLineNumbers, 319 HasInlineFrames: src.HasInlineFrames, 320 } 321 pm.p.Mapping = append(pm.p.Mapping, m) 322 323 // Update memoization tables. 324 if m.BuildID != "" { 325 pm.mappings[bk] = m 326 } 327 if m.File != "" { 328 pm.mappings[pk] = m 329 } 330 mi := mapInfo{m, 0} 331 pm.mappingsByID[src.ID] = mi 332 return mi 333 } 334 335 // key generates encoded strings of Mapping to be used as a key for 336 // maps. The first key represents only the build id, while the second 337 // represents only the file path. 338 func (m *Mapping) key() (buildIDKey, pathKey mappingKey) { 339 // Normalize addresses to handle address space randomization. 340 // Round up to next 4K boundary to avoid minor discrepancies. 341 const mapsizeRounding = 0x1000 342 343 size := m.Limit - m.Start 344 size = size + mapsizeRounding - 1 345 size = size - (size % mapsizeRounding) 346 347 buildIDKey = mappingKey{ 348 size, 349 m.Offset, 350 m.BuildID, 351 } 352 353 pathKey = mappingKey{ 354 size, 355 m.Offset, 356 m.File, 357 } 358 return 359 } 360 361 type mappingKey struct { 362 size, offset uint64 363 buildidIDOrFile string 364 } 365 366 func (pm *profileMerger) mapLine(src Line) Line { 367 ln := Line{ 368 Function: pm.mapFunction(src.Function), 369 Line: src.Line, 370 } 371 return ln 372 } 373 374 func (pm *profileMerger) mapFunction(src *Function) *Function { 375 if src == nil { 376 return nil 377 } 378 if f, ok := pm.functionsByID[src.ID]; ok { 379 return f 380 } 381 k := src.key() 382 if f, ok := pm.functions[k]; ok { 383 pm.functionsByID[src.ID] = f 384 return f 385 } 386 f := &Function{ 387 ID: uint64(len(pm.p.Function) + 1), 388 Name: src.Name, 389 SystemName: src.SystemName, 390 Filename: src.Filename, 391 StartLine: src.StartLine, 392 } 393 pm.functions[k] = f 394 pm.functionsByID[src.ID] = f 395 pm.p.Function = append(pm.p.Function, f) 396 return f 397 } 398 399 // key generates a struct to be used as a key for maps. 400 func (f *Function) key() functionKey { 401 return functionKey{ 402 f.StartLine, 403 f.Name, 404 f.SystemName, 405 f.Filename, 406 } 407 } 408 409 type functionKey struct { 410 startLine int64 411 name, systemName, fileName string 412 } 413 414 // combineHeaders checks that all profiles can be merged and returns 415 // their combined profile. 416 func combineHeaders(srcs []*Profile) (*Profile, error) { 417 for _, s := range srcs[1:] { 418 if err := srcs[0].compatible(s); err != nil { 419 return nil, err 420 } 421 } 422 423 var timeNanos, durationNanos, period int64 424 var comments []string 425 var defaultSampleType string 426 for _, s := range srcs { 427 if timeNanos == 0 || s.TimeNanos < timeNanos { 428 timeNanos = s.TimeNanos 429 } 430 durationNanos += s.DurationNanos 431 if period == 0 || period < s.Period { 432 period = s.Period 433 } 434 comments = append(comments, s.Comments...) 435 if defaultSampleType == "" { 436 defaultSampleType = s.DefaultSampleType 437 } 438 } 439 440 p := &Profile{ 441 SampleType: make([]*ValueType, len(srcs[0].SampleType)), 442 443 DropFrames: srcs[0].DropFrames, 444 KeepFrames: srcs[0].KeepFrames, 445 446 TimeNanos: timeNanos, 447 DurationNanos: durationNanos, 448 PeriodType: srcs[0].PeriodType, 449 Period: period, 450 451 Comments: comments, 452 DefaultSampleType: defaultSampleType, 453 } 454 copy(p.SampleType, srcs[0].SampleType) 455 return p, nil 456 } 457 458 // compatible determines if two profiles can be compared/merged. 459 // returns nil if the profiles are compatible; otherwise an error with 460 // details on the incompatibility. 461 func (p *Profile) compatible(pb *Profile) error { 462 if !equalValueType(p.PeriodType, pb.PeriodType) { 463 return fmt.Errorf("incompatible period types %v and %v", p.PeriodType, pb.PeriodType) 464 } 465 466 if len(p.SampleType) != len(pb.SampleType) { 467 return fmt.Errorf("incompatible sample types %v and %v", p.SampleType, pb.SampleType) 468 } 469 470 for i := range p.SampleType { 471 if !equalValueType(p.SampleType[i], pb.SampleType[i]) { 472 return fmt.Errorf("incompatible sample types %v and %v", p.SampleType, pb.SampleType) 473 } 474 } 475 return nil 476 } 477 478 // equalValueType returns true if the two value types are semantically 479 // equal. It ignores the internal fields used during encode/decode. 480 func equalValueType(st1, st2 *ValueType) bool { 481 return st1.Type == st2.Type && st1.Unit == st2.Unit 482 } 483