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