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