generation.go

Documentation: golang.org/x/exp/trace

     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  // Code generated by "gen.bash" from internal/trace/v2; DO NOT EDIT.
     6  
     7  //go:build go1.21
     8  
     9  package trace
    10  
    11  import (
    12  	"bufio"
    13  	"bytes"
    14  	"cmp"
    15  	"encoding/binary"
    16  	"fmt"
    17  	"io"
    18  	"slices"
    19  	"strings"
    20  
    21  	"golang.org/x/exp/trace/internal/event"
    22  	"golang.org/x/exp/trace/internal/event/go122"
    23  )
    24  
    25  // generation contains all the trace data for a single
    26  // trace generation. It is purely data: it does not
    27  // track any parse state nor does it contain a cursor
    28  // into the generation.
    29  type generation struct {
    30  	gen        uint64
    31  	batches    map[ThreadID][]batch
    32  	cpuSamples []cpuSample
    33  	*evTable
    34  }
    35  
    36  // spilledBatch represents a batch that was read out for the next generation,
    37  // while reading the previous one. It's passed on when parsing the next
    38  // generation.
    39  type spilledBatch struct {
    40  	gen uint64
    41  	*batch
    42  }
    43  
    44  // readGeneration buffers and decodes the structural elements of a trace generation
    45  // out of r. spill is the first batch of the new generation (already buffered and
    46  // parsed from reading the last generation). Returns the generation and the first
    47  // batch read of the next generation, if any.
    48  func readGeneration(r *bufio.Reader, spill *spilledBatch) (*generation, *spilledBatch, error) {
    49  	g := &generation{
    50  		evTable: &evTable{
    51  			pcs: make(map[uint64]frame),
    52  		},
    53  		batches: make(map[ThreadID][]batch),
    54  	}
    55  	// Process the spilled batch.
    56  	if spill != nil {
    57  		g.gen = spill.gen
    58  		if err := processBatch(g, *spill.batch); err != nil {
    59  			return nil, nil, err
    60  		}
    61  		spill = nil
    62  	}
    63  	// Read batches one at a time until we either hit EOF or
    64  	// the next generation.
    65  	for {
    66  		b, gen, err := readBatch(r)
    67  		if err == io.EOF {
    68  			break
    69  		}
    70  		if err != nil {
    71  			return nil, nil, err
    72  		}
    73  		if gen == 0 {
    74  			// 0 is a sentinel used by the runtime, so we'll never see it.
    75  			return nil, nil, fmt.Errorf("invalid generation number %d", gen)
    76  		}
    77  		if g.gen == 0 {
    78  			// Initialize gen.
    79  			g.gen = gen
    80  		}
    81  		if gen == g.gen+1 { // TODO: advance this the same way the runtime does.
    82  			spill = &spilledBatch{gen: gen, batch: &b}
    83  			break
    84  		}
    85  		if gen != g.gen {
    86  			// N.B. Fail as fast as possible if we see this. At first it
    87  			// may seem prudent to be fault-tolerant and assume we have a
    88  			// complete generation, parsing and returning that first. However,
    89  			// if the batches are mixed across generations then it's likely
    90  			// we won't be able to parse this generation correctly at all.
    91  			// Rather than return a cryptic error in that case, indicate the
    92  			// problem as soon as we see it.
    93  			return nil, nil, fmt.Errorf("generations out of order")
    94  		}
    95  		if err := processBatch(g, b); err != nil {
    96  			return nil, nil, err
    97  		}
    98  	}
    99  
   100  	// Check some invariants.
   101  	if g.freq == 0 {
   102  		return nil, nil, fmt.Errorf("no frequency event found")
   103  	}
   104  	// N.B. Trust that the batch order is correct. We can't validate the batch order
   105  	// by timestamp because the timestamps could just be plain wrong. The source of
   106  	// truth is the order things appear in the trace and the partial order sequence
   107  	// numbers on certain events. If it turns out the batch order is actually incorrect
   108  	// we'll very likely fail to advance a partial order from the frontier.
   109  
   110  	// Compactify stacks and strings for better lookup performance later.
   111  	g.stacks.compactify()
   112  	g.strings.compactify()
   113  
   114  	// Validate stacks.
   115  	if err := validateStackStrings(&g.stacks, &g.strings, g.pcs); err != nil {
   116  		return nil, nil, err
   117  	}
   118  
   119  	// Fix up the CPU sample timestamps, now that we have freq.
   120  	for i := range g.cpuSamples {
   121  		s := &g.cpuSamples[i]
   122  		s.time = g.freq.mul(timestamp(s.time))
   123  	}
   124  	// Sort the CPU samples.
   125  	slices.SortFunc(g.cpuSamples, func(a, b cpuSample) int {
   126  		return cmp.Compare(a.time, b.time)
   127  	})
   128  	return g, spill, nil
   129  }
   130  
   131  // processBatch adds the batch to the generation.
   132  func processBatch(g *generation, b batch) error {
   133  	switch {
   134  	case b.isStringsBatch():
   135  		if err := addStrings(&g.strings, b); err != nil {
   136  			return err
   137  		}
   138  	case b.isStacksBatch():
   139  		if err := addStacks(&g.stacks, g.pcs, b); err != nil {
   140  			return err
   141  		}
   142  	case b.isCPUSamplesBatch():
   143  		samples, err := addCPUSamples(g.cpuSamples, b)
   144  		if err != nil {
   145  			return err
   146  		}
   147  		g.cpuSamples = samples
   148  	case b.isFreqBatch():
   149  		freq, err := parseFreq(b)
   150  		if err != nil {
   151  			return err
   152  		}
   153  		if g.freq != 0 {
   154  			return fmt.Errorf("found multiple frequency events")
   155  		}
   156  		g.freq = freq
   157  	default:
   158  		g.batches[b.m] = append(g.batches[b.m], b)
   159  	}
   160  	return nil
   161  }
   162  
   163  // validateStackStrings makes sure all the string references in
   164  // the stack table are present in the string table.
   165  func validateStackStrings(
   166  	stacks *dataTable[stackID, stack],
   167  	strings *dataTable[stringID, string],
   168  	frames map[uint64]frame,
   169  ) error {
   170  	var err error
   171  	stacks.forEach(func(id stackID, stk stack) bool {
   172  		for _, pc := range stk.pcs {
   173  			frame, ok := frames[pc]
   174  			if !ok {
   175  				err = fmt.Errorf("found unknown pc %x for stack %d", pc, id)
   176  				return false
   177  			}
   178  			_, ok = strings.get(frame.funcID)
   179  			if !ok {
   180  				err = fmt.Errorf("found invalid func string ID %d for stack %d", frame.funcID, id)
   181  				return false
   182  			}
   183  			_, ok = strings.get(frame.fileID)
   184  			if !ok {
   185  				err = fmt.Errorf("found invalid file string ID %d for stack %d", frame.fileID, id)
   186  				return false
   187  			}
   188  		}
   189  		return true
   190  	})
   191  	return err
   192  }
   193  
   194  // addStrings takes a batch whose first byte is an EvStrings event
   195  // (indicating that the batch contains only strings) and adds each
   196  // string contained therein to the provided strings map.
   197  func addStrings(stringTable *dataTable[stringID, string], b batch) error {
   198  	if !b.isStringsBatch() {
   199  		return fmt.Errorf("internal error: addStrings called on non-string batch")
   200  	}
   201  	r := bytes.NewReader(b.data)
   202  	hdr, err := r.ReadByte() // Consume the EvStrings byte.
   203  	if err != nil || event.Type(hdr) != go122.EvStrings {
   204  		return fmt.Errorf("missing strings batch header")
   205  	}
   206  
   207  	var sb strings.Builder
   208  	for r.Len() != 0 {
   209  		// Read the header.
   210  		ev, err := r.ReadByte()
   211  		if err != nil {
   212  			return err
   213  		}
   214  		if event.Type(ev) != go122.EvString {
   215  			return fmt.Errorf("expected string event, got %d", ev)
   216  		}
   217  
   218  		// Read the string's ID.
   219  		id, err := binary.ReadUvarint(r)
   220  		if err != nil {
   221  			return err
   222  		}
   223  
   224  		// Read the string's length.
   225  		len, err := binary.ReadUvarint(r)
   226  		if err != nil {
   227  			return err
   228  		}
   229  		if len > go122.MaxStringSize {
   230  			return fmt.Errorf("invalid string size %d, maximum is %d", len, go122.MaxStringSize)
   231  		}
   232  
   233  		// Copy out the string.
   234  		n, err := io.CopyN(&sb, r, int64(len))
   235  		if n != int64(len) {
   236  			return fmt.Errorf("failed to read full string: read %d but wanted %d", n, len)
   237  		}
   238  		if err != nil {
   239  			return fmt.Errorf("copying string data: %w", err)
   240  		}
   241  
   242  		// Add the string to the map.
   243  		s := sb.String()
   244  		sb.Reset()
   245  		if err := stringTable.insert(stringID(id), s); err != nil {
   246  			return err
   247  		}
   248  	}
   249  	return nil
   250  }
   251  
   252  // addStacks takes a batch whose first byte is an EvStacks event
   253  // (indicating that the batch contains only stacks) and adds each
   254  // string contained therein to the provided stacks map.
   255  func addStacks(stackTable *dataTable[stackID, stack], pcs map[uint64]frame, b batch) error {
   256  	if !b.isStacksBatch() {
   257  		return fmt.Errorf("internal error: addStacks called on non-stacks batch")
   258  	}
   259  	r := bytes.NewReader(b.data)
   260  	hdr, err := r.ReadByte() // Consume the EvStacks byte.
   261  	if err != nil || event.Type(hdr) != go122.EvStacks {
   262  		return fmt.Errorf("missing stacks batch header")
   263  	}
   264  
   265  	for r.Len() != 0 {
   266  		// Read the header.
   267  		ev, err := r.ReadByte()
   268  		if err != nil {
   269  			return err
   270  		}
   271  		if event.Type(ev) != go122.EvStack {
   272  			return fmt.Errorf("expected stack event, got %d", ev)
   273  		}
   274  
   275  		// Read the stack's ID.
   276  		id, err := binary.ReadUvarint(r)
   277  		if err != nil {
   278  			return err
   279  		}
   280  
   281  		// Read how many frames are in each stack.
   282  		nFrames, err := binary.ReadUvarint(r)
   283  		if err != nil {
   284  			return err
   285  		}
   286  		if nFrames > go122.MaxFramesPerStack {
   287  			return fmt.Errorf("invalid stack size %d, maximum is %d", nFrames, go122.MaxFramesPerStack)
   288  		}
   289  
   290  		// Each frame consists of 4 fields: pc, funcID (string), fileID (string), line.
   291  		frames := make([]uint64, 0, nFrames)
   292  		for i := uint64(0); i < nFrames; i++ {
   293  			// Read the frame data.
   294  			pc, err := binary.ReadUvarint(r)
   295  			if err != nil {
   296  				return fmt.Errorf("reading frame %d's PC for stack %d: %w", i+1, id, err)
   297  			}
   298  			funcID, err := binary.ReadUvarint(r)
   299  			if err != nil {
   300  				return fmt.Errorf("reading frame %d's funcID for stack %d: %w", i+1, id, err)
   301  			}
   302  			fileID, err := binary.ReadUvarint(r)
   303  			if err != nil {
   304  				return fmt.Errorf("reading frame %d's fileID for stack %d: %w", i+1, id, err)
   305  			}
   306  			line, err := binary.ReadUvarint(r)
   307  			if err != nil {
   308  				return fmt.Errorf("reading frame %d's line for stack %d: %w", i+1, id, err)
   309  			}
   310  			frames = append(frames, pc)
   311  
   312  			if _, ok := pcs[pc]; !ok {
   313  				pcs[pc] = frame{
   314  					pc:     pc,
   315  					funcID: stringID(funcID),
   316  					fileID: stringID(fileID),
   317  					line:   line,
   318  				}
   319  			}
   320  		}
   321  
   322  		// Add the stack to the map.
   323  		if err := stackTable.insert(stackID(id), stack{pcs: frames}); err != nil {
   324  			return err
   325  		}
   326  	}
   327  	return nil
   328  }
   329  
   330  // addCPUSamples takes a batch whose first byte is an EvCPUSamples event
   331  // (indicating that the batch contains only CPU samples) and adds each
   332  // sample contained therein to the provided samples list.
   333  func addCPUSamples(samples []cpuSample, b batch) ([]cpuSample, error) {
   334  	if !b.isCPUSamplesBatch() {
   335  		return nil, fmt.Errorf("internal error: addCPUSamples called on non-CPU-sample batch")
   336  	}
   337  	r := bytes.NewReader(b.data)
   338  	hdr, err := r.ReadByte() // Consume the EvCPUSamples byte.
   339  	if err != nil || event.Type(hdr) != go122.EvCPUSamples {
   340  		return nil, fmt.Errorf("missing CPU samples batch header")
   341  	}
   342  
   343  	for r.Len() != 0 {
   344  		// Read the header.
   345  		ev, err := r.ReadByte()
   346  		if err != nil {
   347  			return nil, err
   348  		}
   349  		if event.Type(ev) != go122.EvCPUSample {
   350  			return nil, fmt.Errorf("expected CPU sample event, got %d", ev)
   351  		}
   352  
   353  		// Read the sample's timestamp.
   354  		ts, err := binary.ReadUvarint(r)
   355  		if err != nil {
   356  			return nil, err
   357  		}
   358  
   359  		// Read the sample's M.
   360  		m, err := binary.ReadUvarint(r)
   361  		if err != nil {
   362  			return nil, err
   363  		}
   364  		mid := ThreadID(m)
   365  
   366  		// Read the sample's P.
   367  		p, err := binary.ReadUvarint(r)
   368  		if err != nil {
   369  			return nil, err
   370  		}
   371  		pid := ProcID(p)
   372  
   373  		// Read the sample's G.
   374  		g, err := binary.ReadUvarint(r)
   375  		if err != nil {
   376  			return nil, err
   377  		}
   378  		goid := GoID(g)
   379  		if g == 0 {
   380  			goid = NoGoroutine
   381  		}
   382  
   383  		// Read the sample's stack.
   384  		s, err := binary.ReadUvarint(r)
   385  		if err != nil {
   386  			return nil, err
   387  		}
   388  
   389  		// Add the sample to the slice.
   390  		samples = append(samples, cpuSample{
   391  			schedCtx: schedCtx{
   392  				M: mid,
   393  				P: pid,
   394  				G: goid,
   395  			},
   396  			time:  Time(ts), // N.B. this is really a "timestamp," not a Time.
   397  			stack: stackID(s),
   398  		})
   399  	}
   400  	return samples, nil
   401  }
   402  
   403  // parseFreq parses out a lone EvFrequency from a batch.
   404  func parseFreq(b batch) (frequency, error) {
   405  	if !b.isFreqBatch() {
   406  		return 0, fmt.Errorf("internal error: parseFreq called on non-frequency batch")
   407  	}
   408  	r := bytes.NewReader(b.data)
   409  	r.ReadByte() // Consume the EvFrequency byte.
   410  
   411  	// Read the frequency. It'll come out as timestamp units per second.
   412  	f, err := binary.ReadUvarint(r)
   413  	if err != nil {
   414  		return 0, err
   415  	}
   416  	// Convert to nanoseconds per timestamp unit.
   417  	return frequency(1.0 / (float64(f) / 1e9)), nil
   418  }
   419
View as plain text