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