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.
17 "internal/trace/v2/event"
18 "internal/trace/v2/event/go122"
21 // generation contains all the trace data for a single
22 // trace generation. It is purely data: it does not
23 // track any parse state nor does it contain a cursor
24 // into the generation.
25 type generation struct {
27 batches map[ThreadID][]batch
28 cpuSamples []cpuSample
32 // spilledBatch represents a batch that was read out for the next generation,
33 // while reading the previous one. It's passed on when parsing the next
35 type spilledBatch struct {
40 // readGeneration buffers and decodes the structural elements of a trace generation
41 // out of r. spill is the first batch of the new generation (already buffered and
42 // parsed from reading the last generation). Returns the generation and the first
43 // batch read of the next generation, if any.
44 func readGeneration(r *bufio.Reader, spill *spilledBatch) (*generation, *spilledBatch, error) {
46 evTable: new(evTable),
47 batches: make(map[ThreadID][]batch),
49 // Process the spilled batch.
52 if err := processBatch(g, *spill.batch); err != nil {
57 // Read batches one at a time until we either hit EOF or
58 // the next generation.
60 b, gen, err := readBatch(r)
68 // 0 is a sentinel used by the runtime, so we'll never see it.
69 return nil, nil, fmt.Errorf("invalid generation number %d", gen)
75 if gen == g.gen+1 { // TODO: advance this the same way the runtime does.
76 spill = &spilledBatch{gen: gen, batch: &b}
80 // N.B. Fail as fast as possible if we see this. At first it
81 // may seem prudent to be fault-tolerant and assume we have a
82 // complete generation, parsing and returning that first. However,
83 // if the batches are mixed across generations then it's likely
84 // we won't be able to parse this generation correctly at all.
85 // Rather than return a cryptic error in that case, indicate the
86 // problem as soon as we see it.
87 return nil, nil, fmt.Errorf("generations out of order")
89 if err := processBatch(g, b); err != nil {
94 // Check some invariants.
96 return nil, nil, fmt.Errorf("no frequency event found")
98 for _, batches := range g.batches {
99 sorted := slices.IsSortedFunc(batches, func(a, b batch) int {
100 return cmp.Compare(a.time, b.time)
103 // TODO(mknyszek): Consider just sorting here.
104 return nil, nil, fmt.Errorf("per-M streams are out-of-order")
108 // Compactify stacks and strings for better lookup performance later.
109 g.stacks.compactify()
110 g.strings.compactify()
113 if err := validateStackStrings(&g.stacks, &g.strings); err != nil {
117 // Fix up the CPU sample timestamps, now that we have freq.
118 for i := range g.cpuSamples {
119 s := &g.cpuSamples[i]
120 s.time = g.freq.mul(timestamp(s.time))
122 // Sort the CPU samples.
123 slices.SortFunc(g.cpuSamples, func(a, b cpuSample) int {
124 return cmp.Compare(a.time, b.time)
129 // processBatch adds the batch to the generation.
130 func processBatch(g *generation, b batch) error {
132 case b.isStringsBatch():
133 if err := addStrings(&g.strings, b); err != nil {
136 case b.isStacksBatch():
137 if err := addStacks(&g.stacks, b); err != nil {
140 case b.isCPUSamplesBatch():
141 samples, err := addCPUSamples(g.cpuSamples, b)
145 g.cpuSamples = samples
146 case b.isFreqBatch():
147 freq, err := parseFreq(b)
152 return fmt.Errorf("found multiple frequency events")
156 g.batches[b.m] = append(g.batches[b.m], b)
161 // validateStackStrings makes sure all the string references in
162 // the stack table are present in the string table.
163 func validateStackStrings(stacks *dataTable[stackID, stack], strings *dataTable[stringID, string]) error {
165 stacks.forEach(func(id stackID, stk stack) bool {
166 for _, frame := range stk.frames {
167 _, ok := strings.get(frame.funcID)
169 err = fmt.Errorf("found invalid func string ID %d for stack %d", frame.funcID, id)
172 _, ok = strings.get(frame.fileID)
174 err = fmt.Errorf("found invalid file string ID %d for stack %d", frame.fileID, id)
183 // addStrings takes a batch whose first byte is an EvStrings event
184 // (indicating that the batch contains only strings) and adds each
185 // string contained therein to the provided strings map.
186 func addStrings(stringTable *dataTable[stringID, string], b batch) error {
187 if !b.isStringsBatch() {
188 return fmt.Errorf("internal error: addStrings called on non-string batch")
190 r := bytes.NewReader(b.data)
191 hdr, err := r.ReadByte() // Consume the EvStrings byte.
192 if err != nil || event.Type(hdr) != go122.EvStrings {
193 return fmt.Errorf("missing strings batch header")
196 var sb strings.Builder
199 ev, err := r.ReadByte()
203 if event.Type(ev) != go122.EvString {
204 return fmt.Errorf("expected string event, got %d", ev)
207 // Read the string's ID.
208 id, err := binary.ReadUvarint(r)
213 // Read the string's length.
214 len, err := binary.ReadUvarint(r)
218 if len > go122.MaxStringSize {
219 return fmt.Errorf("invalid string size %d, maximum is %d", len, go122.MaxStringSize)
222 // Copy out the string.
223 n, err := io.CopyN(&sb, r, int64(len))
225 return fmt.Errorf("failed to read full string: read %d but wanted %d", n, len)
228 return fmt.Errorf("copying string data: %w", err)
231 // Add the string to the map.
234 if err := stringTable.insert(stringID(id), s); err != nil {
241 // addStacks takes a batch whose first byte is an EvStacks event
242 // (indicating that the batch contains only stacks) and adds each
243 // string contained therein to the provided stacks map.
244 func addStacks(stackTable *dataTable[stackID, stack], b batch) error {
245 if !b.isStacksBatch() {
246 return fmt.Errorf("internal error: addStacks called on non-stacks batch")
248 r := bytes.NewReader(b.data)
249 hdr, err := r.ReadByte() // Consume the EvStacks byte.
250 if err != nil || event.Type(hdr) != go122.EvStacks {
251 return fmt.Errorf("missing stacks batch header")
256 ev, err := r.ReadByte()
260 if event.Type(ev) != go122.EvStack {
261 return fmt.Errorf("expected stack event, got %d", ev)
264 // Read the stack's ID.
265 id, err := binary.ReadUvarint(r)
270 // Read how many frames are in each stack.
271 nFrames, err := binary.ReadUvarint(r)
275 if nFrames > go122.MaxFramesPerStack {
276 return fmt.Errorf("invalid stack size %d, maximum is %d", nFrames, go122.MaxFramesPerStack)
279 // Each frame consists of 4 fields: pc, funcID (string), fileID (string), line.
280 frames := make([]frame, 0, nFrames)
281 for i := uint64(0); i < nFrames; i++ {
282 // Read the frame data.
283 pc, err := binary.ReadUvarint(r)
285 return fmt.Errorf("reading frame %d's PC for stack %d: %w", i+1, id, err)
287 funcID, err := binary.ReadUvarint(r)
289 return fmt.Errorf("reading frame %d's funcID for stack %d: %w", i+1, id, err)
291 fileID, err := binary.ReadUvarint(r)
293 return fmt.Errorf("reading frame %d's fileID for stack %d: %w", i+1, id, err)
295 line, err := binary.ReadUvarint(r)
297 return fmt.Errorf("reading frame %d's line for stack %d: %w", i+1, id, err)
299 frames = append(frames, frame{
301 funcID: stringID(funcID),
302 fileID: stringID(fileID),
307 // Add the stack to the map.
308 if err := stackTable.insert(stackID(id), stack{frames: frames}); err != nil {
315 // addCPUSamples takes a batch whose first byte is an EvCPUSamples event
316 // (indicating that the batch contains only CPU samples) and adds each
317 // sample contained therein to the provided samples list.
318 func addCPUSamples(samples []cpuSample, b batch) ([]cpuSample, error) {
319 if !b.isCPUSamplesBatch() {
320 return nil, fmt.Errorf("internal error: addStrings called on non-string batch")
322 r := bytes.NewReader(b.data)
323 hdr, err := r.ReadByte() // Consume the EvCPUSamples byte.
324 if err != nil || event.Type(hdr) != go122.EvCPUSamples {
325 return nil, fmt.Errorf("missing CPU samples batch header")
330 ev, err := r.ReadByte()
334 if event.Type(ev) != go122.EvCPUSample {
335 return nil, fmt.Errorf("expected CPU sample event, got %d", ev)
338 // Read the sample's timestamp.
339 ts, err := binary.ReadUvarint(r)
344 // Read the sample's M.
345 m, err := binary.ReadUvarint(r)
351 // Read the sample's P.
352 p, err := binary.ReadUvarint(r)
358 // Read the sample's G.
359 g, err := binary.ReadUvarint(r)
368 // Read the sample's stack.
369 s, err := binary.ReadUvarint(r)
374 // Add the sample to the slice.
375 samples = append(samples, cpuSample{
381 time: Time(ts), // N.B. this is really a "timestamp," not a Time.
388 // parseFreq parses out a lone EvFrequency from a batch.
389 func parseFreq(b batch) (frequency, error) {
390 if !b.isFreqBatch() {
391 return 0, fmt.Errorf("internal error: parseFreq called on non-frequency batch")
393 r := bytes.NewReader(b.data)
394 r.ReadByte() // Consume the EvFrequency byte.
396 // Read the frequency. It'll come out as timestamp units per second.
397 f, err := binary.ReadUvarint(r)
401 // Convert to nanoseconds per timestamp unit.
402 return frequency(1.0 / (float64(f) / 1e9)), nil