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