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