base.go

     1  // Copyright 2023 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  // This file contains data types that all implementations of the trace format
     6  // parser need to provide to the rest of the package.
     7  
     8  package trace
     9  
    10  import (
    11  	"fmt"
    12  	"math"
    13  	"strings"
    14  
    15  	"internal/trace/tracev2"
    16  	"internal/trace/version"
    17  )
    18  
    19  // timedEventArgs is an array that is able to hold the arguments for any
    20  // timed event.
    21  type timedEventArgs [tracev2.MaxTimedEventArgs - 1]uint64
    22  
    23  // baseEvent is the basic unprocessed event. This serves as a common
    24  // fundamental data structure across.
    25  type baseEvent struct {
    26  	typ  tracev2.EventType
    27  	time Time
    28  	args timedEventArgs
    29  }
    30  
    31  // extra returns a slice representing extra available space in args
    32  // that the parser can use to pass data up into Event.
    33  func (e *baseEvent) extra(v version.Version) []uint64 {
    34  	switch v {
    35  	case version.Go122:
    36  		return e.args[len(tracev2.Specs()[e.typ].Args)-1:]
    37  	}
    38  	panic(fmt.Sprintf("unsupported version: go 1.%d", v))
    39  }
    40  
    41  // evTable contains the per-generation data necessary to
    42  // interpret an individual event.
    43  type evTable struct {
    44  	freq    frequency
    45  	strings dataTable[stringID, string]
    46  	stacks  dataTable[stackID, stack]
    47  	pcs     map[uint64]frame
    48  
    49  	// extraStrings are strings that get generated during
    50  	// parsing but haven't come directly from the trace, so
    51  	// they don't appear in strings.
    52  	extraStrings   []string
    53  	extraStringIDs map[string]extraStringID
    54  	nextExtra      extraStringID
    55  
    56  	// expBatches contains extra unparsed data relevant to a specific experiment.
    57  	expBatches map[tracev2.Experiment][]ExperimentalBatch
    58  }
    59  
    60  // addExtraString adds an extra string to the evTable and returns
    61  // a unique ID for the string in the table.
    62  func (t *evTable) addExtraString(s string) extraStringID {
    63  	if s == "" {
    64  		return 0
    65  	}
    66  	if t.extraStringIDs == nil {
    67  		t.extraStringIDs = make(map[string]extraStringID)
    68  	}
    69  	if id, ok := t.extraStringIDs[s]; ok {
    70  		return id
    71  	}
    72  	t.nextExtra++
    73  	id := t.nextExtra
    74  	t.extraStrings = append(t.extraStrings, s)
    75  	t.extraStringIDs[s] = id
    76  	return id
    77  }
    78  
    79  // getExtraString returns the extra string for the provided ID.
    80  // The ID must have been produced by addExtraString for this evTable.
    81  func (t *evTable) getExtraString(id extraStringID) string {
    82  	if id == 0 {
    83  		return ""
    84  	}
    85  	return t.extraStrings[id-1]
    86  }
    87  
    88  // dataTable is a mapping from EIs to Es.
    89  type dataTable[EI ~uint64, E any] struct {
    90  	present []uint8
    91  	dense   []E
    92  	sparse  map[EI]E
    93  }
    94  
    95  // insert tries to add a mapping from id to s.
    96  //
    97  // Returns an error if a mapping for id already exists, regardless
    98  // of whether or not s is the same in content. This should be used
    99  // for validation during parsing.
   100  func (d *dataTable[EI, E]) insert(id EI, data E) error {
   101  	if d.sparse == nil {
   102  		d.sparse = make(map[EI]E)
   103  	}
   104  	if existing, ok := d.get(id); ok {
   105  		return fmt.Errorf("multiple %Ts with the same ID: id=%d, new=%v, existing=%v", data, id, data, existing)
   106  	}
   107  	d.sparse[id] = data
   108  	return nil
   109  }
   110  
   111  // compactify attempts to compact sparse into dense.
   112  //
   113  // This is intended to be called only once after insertions are done.
   114  func (d *dataTable[EI, E]) compactify() {
   115  	if d.sparse == nil || len(d.dense) != 0 {
   116  		// Already compactified.
   117  		return
   118  	}
   119  	// Find the range of IDs.
   120  	maxID := EI(0)
   121  	minID := ^EI(0)
   122  	for id := range d.sparse {
   123  		if id > maxID {
   124  			maxID = id
   125  		}
   126  		if id < minID {
   127  			minID = id
   128  		}
   129  	}
   130  	if maxID >= math.MaxInt {
   131  		// We can't create a slice big enough to hold maxID elements
   132  		return
   133  	}
   134  	// We're willing to waste at most 2x memory.
   135  	if int(maxID-minID) > max(len(d.sparse), 2*len(d.sparse)) {
   136  		return
   137  	}
   138  	if int(minID) > len(d.sparse) {
   139  		return
   140  	}
   141  	size := int(maxID) + 1
   142  	d.present = make([]uint8, (size+7)/8)
   143  	d.dense = make([]E, size)
   144  	for id, data := range d.sparse {
   145  		d.dense[id] = data
   146  		d.present[id/8] |= uint8(1) << (id % 8)
   147  	}
   148  	d.sparse = nil
   149  }
   150  
   151  // get returns the E for id or false if it doesn't
   152  // exist. This should be used for validation during parsing.
   153  func (d *dataTable[EI, E]) get(id EI) (E, bool) {
   154  	if id == 0 {
   155  		return *new(E), true
   156  	}
   157  	if uint64(id) < uint64(len(d.dense)) {
   158  		if d.present[id/8]&(uint8(1)<<(id%8)) != 0 {
   159  			return d.dense[id], true
   160  		}
   161  	} else if d.sparse != nil {
   162  		if data, ok := d.sparse[id]; ok {
   163  			return data, true
   164  		}
   165  	}
   166  	return *new(E), false
   167  }
   168  
   169  // forEach iterates over all ID/value pairs in the data table.
   170  func (d *dataTable[EI, E]) forEach(yield func(EI, E) bool) bool {
   171  	for id, value := range d.dense {
   172  		if d.present[id/8]&(uint8(1)<<(id%8)) == 0 {
   173  			continue
   174  		}
   175  		if !yield(EI(id), value) {
   176  			return false
   177  		}
   178  	}
   179  	if d.sparse == nil {
   180  		return true
   181  	}
   182  	for id, value := range d.sparse {
   183  		if !yield(id, value) {
   184  			return false
   185  		}
   186  	}
   187  	return true
   188  }
   189  
   190  // mustGet returns the E for id or panics if it fails.
   191  //
   192  // This should only be used if id has already been validated.
   193  func (d *dataTable[EI, E]) mustGet(id EI) E {
   194  	data, ok := d.get(id)
   195  	if !ok {
   196  		panic(fmt.Sprintf("expected id %d in %T table", id, data))
   197  	}
   198  	return data
   199  }
   200  
   201  // frequency is nanoseconds per timestamp unit.
   202  type frequency float64
   203  
   204  // mul multiplies an unprocessed to produce a time in nanoseconds.
   205  func (f frequency) mul(t timestamp) Time {
   206  	return Time(float64(t) * float64(f))
   207  }
   208  
   209  // stringID is an index into the string table for a generation.
   210  type stringID uint64
   211  
   212  // extraStringID is an index into the extra string table for a generation.
   213  type extraStringID uint64
   214  
   215  // stackID is an index into the stack table for a generation.
   216  type stackID uint64
   217  
   218  // cpuSample represents a CPU profiling sample captured by the trace.
   219  type cpuSample struct {
   220  	schedCtx
   221  	time  Time
   222  	stack stackID
   223  }
   224  
   225  // asEvent produces a complete Event from a cpuSample. It needs
   226  // the evTable from the generation that created it.
   227  //
   228  // We don't just store it as an Event in generation to minimize
   229  // the amount of pointer data floating around.
   230  func (s cpuSample) asEvent(table *evTable) Event {
   231  	// TODO(mknyszek): This is go122-specific, but shouldn't be.
   232  	// Generalize this in the future.
   233  	e := Event{
   234  		table: table,
   235  		ctx:   s.schedCtx,
   236  		base: baseEvent{
   237  			typ:  tracev2.EvCPUSample,
   238  			time: s.time,
   239  		},
   240  	}
   241  	e.base.args[0] = uint64(s.stack)
   242  	return e
   243  }
   244  
   245  // stack represents a goroutine stack sample.
   246  type stack struct {
   247  	pcs []uint64
   248  }
   249  
   250  func (s stack) String() string {
   251  	var sb strings.Builder
   252  	for _, frame := range s.pcs {
   253  		fmt.Fprintf(&sb, "\t%#v\n", frame)
   254  	}
   255  	return sb.String()
   256  }
   257  
   258  // frame represents a single stack frame.
   259  type frame struct {
   260  	pc     uint64
   261  	funcID stringID
   262  	fileID stringID
   263  	line   uint64
   264  }
   265
View as plain text