src/internal/trace/v2/order.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 package trace
   6
   7 import (
   8         "fmt"
   9         "strings"
  10
  11         "internal/trace/v2/event"
  12         "internal/trace/v2/event/go122"
  13         "internal/trace/v2/version"
  14 )
  15
  16 // ordering emulates Go scheduler state for both validation and
  17 // for putting events in the right order.
  18 type ordering struct {
  19         gStates     map[GoID]*gState
  20         pStates     map[ProcID]*pState // TODO: The keys are dense, so this can be a slice.
  21         mStates     map[ThreadID]*mState
  22         activeTasks map[TaskID]taskState
  23         gcSeq       uint64
  24         gcState     gcState
  25         initialGen  uint64
  26 }
  27
  28 // advance checks if it's valid to proceed with ev which came from thread m.
  29 //
  30 // Returns the schedCtx at the point of the event, whether it's OK to advance
  31 // with this event, and any error encountered in validation.
  32 //
  33 // It assumes the gen value passed to it is monotonically increasing across calls.
  34 //
  35 // If any error is returned, then the trace is broken and trace parsing must cease.
  36 // If it's not valid to advance with ev, but no error was encountered, the caller
  37 // should attempt to advance with other candidate events from other threads. If the
  38 // caller runs out of candidates, the trace is invalid.
  39 func (o *ordering) advance(ev *baseEvent, evt *evTable, m ThreadID, gen uint64) (schedCtx, bool, error) {
  40         if o.initialGen == 0 {
  41                 // Set the initial gen if necessary.
  42                 o.initialGen = gen
  43         }
  44
  45         var curCtx, newCtx schedCtx
  46         curCtx.M = m
  47         newCtx.M = m
  48
  49         if m == NoThread {
  50                 curCtx.P = NoProc
  51                 curCtx.G = NoGoroutine
  52                 newCtx = curCtx
  53         } else {
  54                 // Pull out or create the mState for this event.
  55                 ms, ok := o.mStates[m]
  56                 if !ok {
  57                         ms = &mState{
  58                                 g: NoGoroutine,
  59                                 p: NoProc,
  60                         }
  61                         o.mStates[m] = ms
  62                 }
  63                 curCtx.P = ms.p
  64                 curCtx.G = ms.g
  65                 newCtx = curCtx
  66                 defer func() {
  67                         // Update the mState for this event.
  68                         ms.p = newCtx.P
  69                         ms.g = newCtx.G
  70                 }()
  71         }
  72
  73         switch typ := ev.typ; typ {
  74         // Handle procs.
  75         case go122.EvProcStatus:
  76                 pid := ProcID(ev.args[0])
  77                 status := go122.ProcStatus(ev.args[1])
  78                 oldState := go122ProcStatus2ProcState[status]
  79                 if s, ok := o.pStates[pid]; ok {
  80                         if status == go122.ProcSyscallAbandoned && s.status == go122.ProcSyscall {
  81                                 // ProcSyscallAbandoned is a special case of ProcSyscall. It indicates a
  82                                 // potential loss of information, but if we're already in ProcSyscall,
  83                                 // we haven't lost the relevant information. Promote the status and advance.
  84                                 oldState = ProcRunning
  85                                 ev.args[1] = uint64(go122.ProcSyscall)
  86                         } else if s.status != status {
  87                                 return curCtx, false, fmt.Errorf("inconsistent status for proc %d: old %v vs. new %v", pid, s.status, status)
  88                         }
  89                         s.seq = makeSeq(gen, 0) // Reset seq.
  90                 } else {
  91                         o.pStates[pid] = &pState{id: pid, status: status, seq: makeSeq(gen, 0)}
  92                         if gen == o.initialGen {
  93                                 oldState = ProcUndetermined
  94                         } else {
  95                                 oldState = ProcNotExist
  96                         }
  97                 }
  98                 ev.extra(version.Go122)[0] = uint64(oldState) // Smuggle in the old state for StateTransition.
  99
 100                 // Bind the proc to the new context, if it's running.
 101                 if status == go122.ProcRunning || status == go122.ProcSyscall {
 102                         newCtx.P = pid
 103                 }
 104                 // Set the current context to the state of the M current running this G. Otherwise
 105                 // we'll emit a Running -> Running event that doesn't correspond to the right M.
 106                 if status == go122.ProcSyscallAbandoned && oldState != ProcUndetermined {
 107                         // N.B. This is slow but it should be fairly rare.
 108                         found := false
 109                         for mid, ms := range o.mStates {
 110                                 if ms.p == pid {
 111                                         curCtx.M = mid
 112                                         curCtx.P = pid
 113                                         curCtx.G = ms.g
 114                                         found = true
 115                                 }
 116                         }
 117                         if !found {
 118                                 return curCtx, false, fmt.Errorf("failed to find sched context for proc %d that's about to be stolen", pid)
 119                         }
 120                 }
 121                 return curCtx, true, nil
 122         case go122.EvProcStart:
 123                 pid := ProcID(ev.args[0])
 124                 seq := makeSeq(gen, ev.args[1])
 125
 126                 // Try to advance. We might fail here due to sequencing, because the P hasn't
 127                 // had a status emitted, or because we already have a P and we're in a syscall,
 128                 // and we haven't observed that it was stolen from us yet.
 129                 state, ok := o.pStates[pid]
 130                 if !ok || state.status != go122.ProcIdle || !seq.succeeds(state.seq) || curCtx.P != NoProc {
 131                         // We can't make an inference as to whether this is bad. We could just be seeing
 132                         // a ProcStart on a different M before the proc's state was emitted, or before we
 133                         // got to the right point in the trace.
 134                         //
 135                         // Note that we also don't advance here if we have a P and we're in a syscall.
 136                         return curCtx, false, nil
 137                 }
 138                 // We can advance this P. Check some invariants.
 139                 //
 140                 // We might have a goroutine if a goroutine is exiting a syscall.
 141                 reqs := event.SchedReqs{Thread: event.MustHave, Proc: event.MustNotHave, Goroutine: event.MayHave}
 142                 if err := validateCtx(curCtx, reqs); err != nil {
 143                         return curCtx, false, err
 144                 }
 145                 state.status = go122.ProcRunning
 146                 state.seq = seq
 147                 newCtx.P = pid
 148                 return curCtx, true, nil
 149         case go122.EvProcStop:
 150                 // We must be able to advance this P.
 151                 //
 152                 // There are 2 ways a P can stop: ProcStop and ProcSteal. ProcStop is used when the P
 153                 // is stopped by the same M that started it, while ProcSteal is used when another M
 154                 // steals the P by stopping it from a distance.
 155                 //
 156                 // Since a P is bound to an M, and we're stopping on the same M we started, it must
 157                 // always be possible to advance the current M's P from a ProcStop. This is also why
 158                 // ProcStop doesn't need a sequence number.
 159                 state, ok := o.pStates[curCtx.P]
 160                 if !ok {
 161                         return curCtx, false, fmt.Errorf("event %s for proc (%v) that doesn't exist", go122.EventString(typ), curCtx.P)
 162                 }
 163                 if state.status != go122.ProcRunning && state.status != go122.ProcSyscall {
 164                         return curCtx, false, fmt.Errorf("%s event for proc that's not %s or %s", go122.EventString(typ), go122.ProcRunning, go122.ProcSyscall)
 165                 }
 166                 reqs := event.SchedReqs{Thread: event.MustHave, Proc: event.MustHave, Goroutine: event.MayHave}
 167                 if err := validateCtx(curCtx, reqs); err != nil {
 168                         return curCtx, false, err
 169                 }
 170                 state.status = go122.ProcIdle
 171                 newCtx.P = NoProc
 172                 return curCtx, true, nil
 173         case go122.EvProcSteal:
 174                 pid := ProcID(ev.args[0])
 175                 seq := makeSeq(gen, ev.args[1])
 176                 state, ok := o.pStates[pid]
 177                 if !ok || (state.status != go122.ProcSyscall && state.status != go122.ProcSyscallAbandoned) || !seq.succeeds(state.seq) {
 178                         // We can't make an inference as to whether this is bad. We could just be seeing
 179                         // a ProcStart on a different M before the proc's state was emitted, or before we
 180                         // got to the right point in the trace.
 181                         return curCtx, false, nil
 182                 }
 183                 // We can advance this P. Check some invariants.
 184                 reqs := event.SchedReqs{Thread: event.MustHave, Proc: event.MayHave, Goroutine: event.MayHave}
 185                 if err := validateCtx(curCtx, reqs); err != nil {
 186                         return curCtx, false, err
 187                 }
 188                 // Smuggle in the P state that let us advance so we can surface information to the event.
 189                 // Specifically, we need to make sure that the event is interpreted not as a transition of
 190                 // ProcRunning -> ProcIdle but ProcIdle -> ProcIdle instead.
 191                 //
 192                 // ProcRunning is binding, but we may be running with a P on the current M and we can't
 193                 // bind another P. This P is about to go ProcIdle anyway.
 194                 oldStatus := state.status
 195                 ev.extra(version.Go122)[0] = uint64(oldStatus)
 196
 197                 // Update the P's status and sequence number.
 198                 state.status = go122.ProcIdle
 199                 state.seq = seq
 200
 201                 // If we've lost information then don't try to do anything with the M.
 202                 // It may have moved on and we can't be sure.
 203                 if oldStatus == go122.ProcSyscallAbandoned {
 204                         return curCtx, true, nil
 205                 }
 206
 207                 // Validate that the M we're stealing from is what we expect.
 208                 mid := ThreadID(ev.args[2]) // The M we're stealing from.
 209                 mState, ok := o.mStates[mid]
 210                 if !ok {
 211                         return curCtx, false, fmt.Errorf("stole proc from non-existent thread %d", mid)
 212                 }
 213
 214                 // Make sure we're actually stealing the right P.
 215                 if mState.p != pid {
 216                         return curCtx, false, fmt.Errorf("tried to steal proc %d from thread %d, but got proc %d instead", pid, mid, mState.p)
 217                 }
 218
 219                 // Tell the M it has no P so it can proceed.
 220                 //
 221                 // This is safe because we know the P was in a syscall and
 222                 // the other M must be trying to get out of the syscall.
 223                 // GoSyscallEndBlocked cannot advance until the corresponding
 224                 // M loses its P.
 225                 mState.p = NoProc
 226                 return curCtx, true, nil
 227
 228         // Handle goroutines.
 229         case go122.EvGoStatus:
 230                 gid := GoID(ev.args[0])
 231                 mid := ThreadID(ev.args[1])
 232                 status := go122.GoStatus(ev.args[2])
 233                 oldState := go122GoStatus2GoState[status]
 234                 if s, ok := o.gStates[gid]; ok {
 235                         if s.status != status {
 236                                 return curCtx, false, fmt.Errorf("inconsistent status for goroutine %d: old %v vs. new %v", gid, s.status, status)
 237                         }
 238                         s.seq = makeSeq(gen, 0) // Reset seq.
 239                 } else if gen == o.initialGen {
 240                         // Set the state.
 241                         o.gStates[gid] = &gState{id: gid, status: status, seq: makeSeq(gen, 0)}
 242                         oldState = GoUndetermined
 243                 } else {
 244                         return curCtx, false, fmt.Errorf("found goroutine status for new goroutine after the first generation: id=%v status=%v", gid, status)
 245                 }
 246                 ev.extra(version.Go122)[0] = uint64(oldState) // Smuggle in the old state for StateTransition.
 247
 248                 switch status {
 249                 case go122.GoRunning:
 250                         // Bind the goroutine to the new context, since it's running.
 251                         newCtx.G = gid
 252                 case go122.GoSyscall:
 253                         if mid == NoThread {
 254                                 return curCtx, false, fmt.Errorf("found goroutine %d in syscall without a thread", gid)
 255                         }
 256                         // Is the syscall on this thread? If so, bind it to the context.
 257                         // Otherwise, we're talking about a G sitting in a syscall on an M.
 258                         // Validate the named M.
 259                         if mid == curCtx.M {
 260                                 newCtx.G = gid
 261                                 break
 262                         }
 263                         // Now we're talking about a thread and goroutine that have been
 264                         // blocked on a syscall for the entire generation. This case must
 265                         // not have a P; the runtime makes sure that all Ps are traced at
 266                         // the beginning of a generation, which involves taking a P back
 267                         // from every thread.
 268                         ms, ok := o.mStates[mid]
 269                         if ok {
 270                                 // This M has been seen. That means we must have seen this
 271                                 // goroutine go into a syscall on this thread at some point.
 272                                 if ms.g != gid {
 273                                         // But the G on the M doesn't match. Something's wrong.
 274                                         return curCtx, false, fmt.Errorf("inconsistent thread for syscalling goroutine %d: thread has goroutine %d", gid, ms.g)
 275                                 }
 276                                 // This case is just a Syscall->Syscall event, which needs to
 277                                 // appear as having the G currently bound to this M.
 278                                 curCtx.G = ms.g
 279                         } else if !ok {
 280                                 // The M hasn't been seen yet. That means this goroutine
 281                                 // has just been sitting in a syscall on this M. Create
 282                                 // a state for it.
 283                                 o.mStates[mid] = &mState{g: gid, p: NoProc}
 284                                 // Don't set curCtx.G in this case because this event is the
 285                                 // binding event (and curCtx represents the "before" state).
 286                         }
 287                         // Update the current context to the M we're talking about.
 288                         curCtx.M = mid
 289                 }
 290                 return curCtx, true, nil
 291         case go122.EvGoCreate:
 292                 // Goroutines must be created on a running P, but may or may not be created
 293                 // by a running goroutine.
 294                 reqs := event.SchedReqs{Thread: event.MustHave, Proc: event.MustHave, Goroutine: event.MayHave}
 295                 if err := validateCtx(curCtx, reqs); err != nil {
 296                         return curCtx, false, err
 297                 }
 298                 // If we have a goroutine, it must be running.
 299                 if state, ok := o.gStates[curCtx.G]; ok && state.status != go122.GoRunning {
 300                         return curCtx, false, fmt.Errorf("%s event for goroutine that's not %s", go122.EventString(typ), GoRunning)
 301                 }
 302                 // This goroutine created another. Add a state for it.
 303                 newgid := GoID(ev.args[0])
 304                 if _, ok := o.gStates[newgid]; ok {
 305                         return curCtx, false, fmt.Errorf("tried to create goroutine (%v) that already exists", newgid)
 306                 }
 307                 o.gStates[newgid] = &gState{id: newgid, status: go122.GoRunnable, seq: makeSeq(gen, 0)}
 308                 return curCtx, true, nil
 309         case go122.EvGoDestroy, go122.EvGoStop, go122.EvGoBlock, go122.EvGoSyscallBegin:
 310                 // These are goroutine events that all require an active running
 311                 // goroutine on some thread. They must *always* be advance-able,
 312                 // since running goroutines are bound to their M.
 313                 if err := validateCtx(curCtx, event.UserGoReqs); err != nil {
 314                         return curCtx, false, err
 315                 }
 316                 state, ok := o.gStates[curCtx.G]
 317                 if !ok {
 318                         return curCtx, false, fmt.Errorf("event %s for goroutine (%v) that doesn't exist", go122.EventString(typ), curCtx.G)
 319                 }
 320                 if state.status != go122.GoRunning {
 321                         return curCtx, false, fmt.Errorf("%s event for goroutine that's not %s", go122.EventString(typ), GoRunning)
 322                 }
 323                 // Handle each case slightly differently; we just group them together
 324                 // because they have shared preconditions.
 325                 switch typ {
 326                 case go122.EvGoDestroy:
 327                         // This goroutine is exiting itself.
 328                         delete(o.gStates, curCtx.G)
 329                         newCtx.G = NoGoroutine
 330                 case go122.EvGoStop:
 331                         // Goroutine stopped (yielded). It's runnable but not running on this M.
 332                         state.status = go122.GoRunnable
 333                         newCtx.G = NoGoroutine
 334                 case go122.EvGoBlock:
 335                         // Goroutine blocked. It's waiting now and not running on this M.
 336                         state.status = go122.GoWaiting
 337                         newCtx.G = NoGoroutine
 338                 case go122.EvGoSyscallBegin:
 339                         // Goroutine entered a syscall. It's still running on this P and M.
 340                         state.status = go122.GoSyscall
 341                         pState, ok := o.pStates[curCtx.P]
 342                         if !ok {
 343                                 return curCtx, false, fmt.Errorf("uninitialized proc %d found during %s", curCtx.P, go122.EventString(typ))
 344                         }
 345                         pState.status = go122.ProcSyscall
 346                 }
 347                 return curCtx, true, nil
 348         case go122.EvGoStart:
 349                 gid := GoID(ev.args[0])
 350                 seq := makeSeq(gen, ev.args[1])
 351                 state, ok := o.gStates[gid]
 352                 if !ok || state.status != go122.GoRunnable || !seq.succeeds(state.seq) {
 353                         // We can't make an inference as to whether this is bad. We could just be seeing
 354                         // a GoStart on a different M before the goroutine was created, before it had its
 355                         // state emitted, or before we got to the right point in the trace yet.
 356                         return curCtx, false, nil
 357                 }
 358                 // We can advance this goroutine. Check some invariants.
 359                 reqs := event.SchedReqs{Thread: event.MustHave, Proc: event.MustHave, Goroutine: event.MustNotHave}
 360                 if err := validateCtx(curCtx, reqs); err != nil {
 361                         return curCtx, false, err
 362                 }
 363                 state.status = go122.GoRunning
 364                 state.seq = seq
 365                 newCtx.G = gid
 366                 return curCtx, true, nil
 367         case go122.EvGoUnblock:
 368                 // N.B. These both reference the goroutine to unblock, not the current goroutine.
 369                 gid := GoID(ev.args[0])
 370                 seq := makeSeq(gen, ev.args[1])
 371                 state, ok := o.gStates[gid]
 372                 if !ok || state.status != go122.GoWaiting || !seq.succeeds(state.seq) {
 373                         // We can't make an inference as to whether this is bad. We could just be seeing
 374                         // a GoUnblock on a different M before the goroutine was created and blocked itself,
 375                         // before it had its state emitted, or before we got to the right point in the trace yet.
 376                         return curCtx, false, nil
 377                 }
 378                 state.status = go122.GoRunnable
 379                 state.seq = seq
 380                 // N.B. No context to validate. Basically anything can unblock
 381                 // a goroutine (e.g. sysmon).
 382                 return curCtx, true, nil
 383         case go122.EvGoSyscallEnd:
 384                 // This event is always advance-able because it happens on the same
 385                 // thread that EvGoSyscallStart happened, and the goroutine can't leave
 386                 // that thread until its done.
 387                 if err := validateCtx(curCtx, event.UserGoReqs); err != nil {
 388                         return curCtx, false, err
 389                 }
 390                 state, ok := o.gStates[curCtx.G]
 391                 if !ok {
 392                         return curCtx, false, fmt.Errorf("event %s for goroutine (%v) that doesn't exist", go122.EventString(typ), curCtx.G)
 393                 }
 394                 if state.status != go122.GoSyscall {
 395                         return curCtx, false, fmt.Errorf("%s event for goroutine that's not %s", go122.EventString(typ), GoRunning)
 396                 }
 397                 state.status = go122.GoRunning
 398
 399                 // Transfer the P back to running from syscall.
 400                 pState, ok := o.pStates[curCtx.P]
 401                 if !ok {
 402                         return curCtx, false, fmt.Errorf("uninitialized proc %d found during %s", curCtx.P, go122.EventString(typ))
 403                 }
 404                 if pState.status != go122.ProcSyscall {
 405                         return curCtx, false, fmt.Errorf("expected proc %d in state %v, but got %v instead", curCtx.P, go122.ProcSyscall, pState.status)
 406                 }
 407                 pState.status = go122.ProcRunning
 408                 return curCtx, true, nil
 409         case go122.EvGoSyscallEndBlocked:
 410                 // This event becomes advanceable when its P is not in a syscall state
 411                 // (lack of a P altogether is also acceptable for advancing).
 412                 // The transfer out of ProcSyscall can happen either voluntarily via
 413                 // ProcStop or involuntarily via ProcSteal. We may also acquire a new P
 414                 // before we get here (after the transfer out) but that's OK: that new
 415                 // P won't be in the ProcSyscall state anymore.
 416                 //
 417                 // Basically: while we have a preemptible P, don't advance, because we
 418                 // *know* from the event that we're going to lose it at some point during
 419                 // the syscall. We shouldn't advance until that happens.
 420                 if curCtx.P != NoProc {
 421                         pState, ok := o.pStates[curCtx.P]
 422                         if !ok {
 423                                 return curCtx, false, fmt.Errorf("uninitialized proc %d found during %s", curCtx.P, go122.EventString(typ))
 424                         }
 425                         if pState.status == go122.ProcSyscall {
 426                                 return curCtx, false, nil
 427                         }
 428                 }
 429                 // As mentioned above, we may have a P here if we ProcStart
 430                 // before this event.
 431                 if err := validateCtx(curCtx, event.SchedReqs{Thread: event.MustHave, Proc: event.MayHave, Goroutine: event.MustHave}); err != nil {
 432                         return curCtx, false, err
 433                 }
 434                 state, ok := o.gStates[curCtx.G]
 435                 if !ok {
 436                         return curCtx, false, fmt.Errorf("event %s for goroutine (%v) that doesn't exist", go122.EventString(typ), curCtx.G)
 437                 }
 438                 if state.status != go122.GoSyscall {
 439                         return curCtx, false, fmt.Errorf("%s event for goroutine that's not %s", go122.EventString(typ), GoRunning)
 440                 }
 441                 newCtx.G = NoGoroutine
 442                 state.status = go122.GoRunnable
 443                 return curCtx, true, nil
 444         case go122.EvGoCreateSyscall:
 445                 // This event indicates that a goroutine is effectively
 446                 // being created out of a cgo callback. Such a goroutine
 447                 // is 'created' in the syscall state.
 448                 if err := validateCtx(curCtx, event.SchedReqs{Thread: event.MustHave, Proc: event.MustNotHave, Goroutine: event.MustNotHave}); err != nil {
 449                         return curCtx, false, err
 450                 }
 451                 // This goroutine is effectively being created. Add a state for it.
 452                 newgid := GoID(ev.args[0])
 453                 if _, ok := o.gStates[newgid]; ok {
 454                         return curCtx, false, fmt.Errorf("tried to create goroutine (%v) in syscall that already exists", newgid)
 455                 }
 456                 o.gStates[newgid] = &gState{id: newgid, status: go122.GoSyscall, seq: makeSeq(gen, 0)}
 457                 // Goroutine is executing. Bind it to the context.
 458                 newCtx.G = newgid
 459                 return curCtx, true, nil
 460         case go122.EvGoDestroySyscall:
 461                 // This event indicates that a goroutine created for a
 462                 // cgo callback is disappearing, either because the callback
 463                 // ending or the C thread that called it is being destroyed.
 464                 //
 465                 // Note: we might have a P here. The P might not be released
 466                 // eagerly by the runtime, and it might get stolen back later
 467                 // (or never again, if the program is going to exit).
 468                 if err := validateCtx(curCtx, event.SchedReqs{Thread: event.MustHave, Proc: event.MayHave, Goroutine: event.MustHave}); err != nil {
 469                         return curCtx, false, err
 470                 }
 471                 // Check to make sure the goroutine exists in the right state.
 472                 state, ok := o.gStates[curCtx.G]
 473                 if !ok {
 474                         return curCtx, false, fmt.Errorf("event %s for goroutine (%v) that doesn't exist", go122.EventString(typ), curCtx.G)
 475                 }
 476                 if state.status != go122.GoSyscall {
 477                         return curCtx, false, fmt.Errorf("%s event for goroutine that's not %v", go122.EventString(typ), GoSyscall)
 478                 }
 479                 // This goroutine is exiting itself.
 480                 delete(o.gStates, curCtx.G)
 481                 newCtx.G = NoGoroutine
 482                 return curCtx, true, nil
 483
 484         // Handle tasks. Tasks are interesting because:
 485         // - There's no Begin event required to reference a task.
 486         // - End for a particular task ID can appear multiple times.
 487         // As a result, there's very little to validate. The only
 488         // thing we have to be sure of is that a task didn't begin
 489         // after it had already begun. Task IDs are allowed to be
 490         // reused, so we don't care about a Begin after an End.
 491         case go122.EvUserTaskBegin:
 492                 id := TaskID(ev.args[0])
 493                 if _, ok := o.activeTasks[id]; ok {
 494                         return curCtx, false, fmt.Errorf("task ID conflict: %d", id)
 495                 }
 496                 // Get the parent ID, but don't validate it. There's no guarantee
 497                 // we actually have information on whether it's active.
 498                 parentID := TaskID(ev.args[1])
 499
 500                 // Validate the name and record it. We'll need to pass it through to
 501                 // EvUserTaskEnd.
 502                 nameID := stringID(ev.args[2])
 503                 name, ok := evt.strings.get(nameID)
 504                 if !ok {
 505                         return curCtx, false, fmt.Errorf("invalid string ID %v for %v event", nameID, typ)
 506                 }
 507                 o.activeTasks[id] = taskState{name: name, parentID: parentID}
 508                 return curCtx, true, validateCtx(curCtx, event.UserGoReqs)
 509         case go122.EvUserTaskEnd:
 510                 id := TaskID(ev.args[0])
 511                 if ts, ok := o.activeTasks[id]; ok {
 512                         // Smuggle the task info. This may happen in a different generation,
 513                         // which may not have the name in its string table. Add it to the extra
 514                         // strings table so we can look it up later.
 515                         ev.extra(version.Go122)[0] = uint64(ts.parentID)
 516                         ev.extra(version.Go122)[1] = uint64(evt.addExtraString(ts.name))
 517                         delete(o.activeTasks, id)
 518                 } else {
 519                         // Explicitly clear the task info.
 520                         ev.extra(version.Go122)[0] = uint64(NoTask)
 521                         ev.extra(version.Go122)[1] = uint64(evt.addExtraString(""))
 522                 }
 523                 return curCtx, true, validateCtx(curCtx, event.UserGoReqs)
 524
 525         // Handle user regions.
 526         case go122.EvUserRegionBegin:
 527                 if err := validateCtx(curCtx, event.UserGoReqs); err != nil {
 528                         return curCtx, false, err
 529                 }
 530                 tid := TaskID(ev.args[0])
 531                 nameID := stringID(ev.args[1])
 532                 name, ok := evt.strings.get(nameID)
 533                 if !ok {
 534                         return curCtx, false, fmt.Errorf("invalid string ID %v for %v event", nameID, typ)
 535                 }
 536                 if err := o.gStates[curCtx.G].beginRegion(userRegion{tid, name}); err != nil {
 537                         return curCtx, false, err
 538                 }
 539                 return curCtx, true, nil
 540         case go122.EvUserRegionEnd:
 541                 if err := validateCtx(curCtx, event.UserGoReqs); err != nil {
 542                         return curCtx, false, err
 543                 }
 544                 tid := TaskID(ev.args[0])
 545                 nameID := stringID(ev.args[1])
 546                 name, ok := evt.strings.get(nameID)
 547                 if !ok {
 548                         return curCtx, false, fmt.Errorf("invalid string ID %v for %v event", nameID, typ)
 549                 }
 550                 if err := o.gStates[curCtx.G].endRegion(userRegion{tid, name}); err != nil {
 551                         return curCtx, false, err
 552                 }
 553                 return curCtx, true, nil
 554
 555         // Handle the GC mark phase.
 556         //
 557         // We have sequence numbers for both start and end because they
 558         // can happen on completely different threads. We want an explicit
 559         // partial order edge between start and end here, otherwise we're
 560         // relying entirely on timestamps to make sure we don't advance a
 561         // GCEnd for a _different_ GC cycle if timestamps are wildly broken.
 562         case go122.EvGCActive:
 563                 seq := ev.args[0]
 564                 if gen == o.initialGen {
 565                         if o.gcState != gcUndetermined {
 566                                 return curCtx, false, fmt.Errorf("GCActive in the first generation isn't first GC event")
 567                         }
 568                         o.gcSeq = seq
 569                         o.gcState = gcRunning
 570                         return curCtx, true, nil
 571                 }
 572                 if seq != o.gcSeq+1 {
 573                         // This is not the right GC cycle.
 574                         return curCtx, false, nil
 575                 }
 576                 if o.gcState != gcRunning {
 577                         return curCtx, false, fmt.Errorf("encountered GCActive while GC was not in progress")
 578                 }
 579                 o.gcSeq = seq
 580                 if err := validateCtx(curCtx, event.UserGoReqs); err != nil {
 581                         return curCtx, false, err
 582                 }
 583                 return curCtx, true, nil
 584         case go122.EvGCBegin:
 585                 seq := ev.args[0]
 586                 if o.gcState == gcUndetermined {
 587                         o.gcSeq = seq
 588                         o.gcState = gcRunning
 589                         return curCtx, true, nil
 590                 }
 591                 if seq != o.gcSeq+1 {
 592                         // This is not the right GC cycle.
 593                         return curCtx, false, nil
 594                 }
 595                 if o.gcState == gcRunning {
 596                         return curCtx, false, fmt.Errorf("encountered GCBegin while GC was already in progress")
 597                 }
 598                 o.gcSeq = seq
 599                 o.gcState = gcRunning
 600                 if err := validateCtx(curCtx, event.UserGoReqs); err != nil {
 601                         return curCtx, false, err
 602                 }
 603                 return curCtx, true, nil
 604         case go122.EvGCEnd:
 605                 seq := ev.args[0]
 606                 if seq != o.gcSeq+1 {
 607                         // This is not the right GC cycle.
 608                         return curCtx, false, nil
 609                 }
 610                 if o.gcState == gcNotRunning {
 611                         return curCtx, false, fmt.Errorf("encountered GCEnd when GC was not in progress")
 612                 }
 613                 if o.gcState == gcUndetermined {
 614                         return curCtx, false, fmt.Errorf("encountered GCEnd when GC was in an undetermined state")
 615                 }
 616                 o.gcSeq = seq
 617                 o.gcState = gcNotRunning
 618                 if err := validateCtx(curCtx, event.UserGoReqs); err != nil {
 619                         return curCtx, false, err
 620                 }
 621                 return curCtx, true, nil
 622
 623         // Handle simple instantaneous events that require a G.
 624         case go122.EvGoLabel, go122.EvProcsChange, go122.EvUserLog:
 625                 if err := validateCtx(curCtx, event.UserGoReqs); err != nil {
 626                         return curCtx, false, err
 627                 }
 628                 return curCtx, true, nil
 629
 630         // Handle allocation states, which don't require a G.
 631         case go122.EvHeapAlloc, go122.EvHeapGoal:
 632                 if err := validateCtx(curCtx, event.SchedReqs{Thread: event.MustHave, Proc: event.MustHave, Goroutine: event.MayHave}); err != nil {
 633                         return curCtx, false, err
 634                 }
 635                 return curCtx, true, nil
 636
 637         // Handle sweep, which is bound to a P and doesn't require a G.
 638         case go122.EvGCSweepBegin:
 639                 if err := validateCtx(curCtx, event.SchedReqs{Thread: event.MustHave, Proc: event.MustHave, Goroutine: event.MayHave}); err != nil {
 640                         return curCtx, false, err
 641                 }
 642                 if err := o.pStates[curCtx.P].beginRange(makeRangeType(typ, 0)); err != nil {
 643                         return curCtx, false, err
 644                 }
 645                 return curCtx, true, nil
 646         case go122.EvGCSweepActive:
 647                 pid := ProcID(ev.args[0])
 648                 // N.B. In practice Ps can't block while they're sweeping, so this can only
 649                 // ever reference curCtx.P. However, be lenient about this like we are with
 650                 // GCMarkAssistActive; there's no reason the runtime couldn't change to block
 651                 // in the middle of a sweep.
 652                 if err := o.pStates[pid].activeRange(makeRangeType(typ, 0), gen == o.initialGen); err != nil {
 653                         return curCtx, false, err
 654                 }
 655                 return curCtx, true, nil
 656         case go122.EvGCSweepEnd:
 657                 if err := validateCtx(curCtx, event.SchedReqs{Thread: event.MustHave, Proc: event.MustHave, Goroutine: event.MayHave}); err != nil {
 658                         return curCtx, false, err
 659                 }
 660                 _, err := o.pStates[curCtx.P].endRange(typ)
 661                 if err != nil {
 662                         return curCtx, false, err
 663                 }
 664                 return curCtx, true, nil
 665
 666         // Handle special goroutine-bound event ranges.
 667         case go122.EvSTWBegin, go122.EvGCMarkAssistBegin:
 668                 if err := validateCtx(curCtx, event.UserGoReqs); err != nil {
 669                         return curCtx, false, err
 670                 }
 671                 desc := stringID(0)
 672                 if typ == go122.EvSTWBegin {
 673                         desc = stringID(ev.args[0])
 674                 }
 675                 if err := o.gStates[curCtx.G].beginRange(makeRangeType(typ, desc)); err != nil {
 676                         return curCtx, false, err
 677                 }
 678                 return curCtx, true, nil
 679         case go122.EvGCMarkAssistActive:
 680                 gid := GoID(ev.args[0])
 681                 // N.B. Like GoStatus, this can happen at any time, because it can
 682                 // reference a non-running goroutine. Don't check anything about the
 683                 // current scheduler context.
 684                 if err := o.gStates[gid].activeRange(makeRangeType(typ, 0), gen == o.initialGen); err != nil {
 685                         return curCtx, false, err
 686                 }
 687                 return curCtx, true, nil
 688         case go122.EvSTWEnd, go122.EvGCMarkAssistEnd:
 689                 if err := validateCtx(curCtx, event.UserGoReqs); err != nil {
 690                         return curCtx, false, err
 691                 }
 692                 desc, err := o.gStates[curCtx.G].endRange(typ)
 693                 if err != nil {
 694                         return curCtx, false, err
 695                 }
 696                 if typ == go122.EvSTWEnd {
 697                         // Smuggle the kind into the event.
 698                         // Don't use ev.extra here so we have symmetry with STWBegin.
 699                         ev.args[0] = uint64(desc)
 700                 }
 701                 return curCtx, true, nil
 702         }
 703         return curCtx, false, fmt.Errorf("bad event type found while ordering: %v", ev.typ)
 704 }
 705
 706 // schedCtx represents the scheduling resources associated with an event.
 707 type schedCtx struct {
 708         G GoID
 709         P ProcID
 710         M ThreadID
 711 }
 712
 713 // validateCtx ensures that ctx conforms to some reqs, returning an error if
 714 // it doesn't.
 715 func validateCtx(ctx schedCtx, reqs event.SchedReqs) error {
 716         // Check thread requirements.
 717         if reqs.Thread == event.MustHave && ctx.M == NoThread {
 718                 return fmt.Errorf("expected a thread but didn't have one")
 719         } else if reqs.Thread == event.MustNotHave && ctx.M != NoThread {
 720                 return fmt.Errorf("expected no thread but had one")
 721         }
 722
 723         // Check proc requirements.
 724         if reqs.Proc == event.MustHave && ctx.P == NoProc {
 725                 return fmt.Errorf("expected a proc but didn't have one")
 726         } else if reqs.Proc == event.MustNotHave && ctx.P != NoProc {
 727                 return fmt.Errorf("expected no proc but had one")
 728         }
 729
 730         // Check goroutine requirements.
 731         if reqs.Goroutine == event.MustHave && ctx.G == NoGoroutine {
 732                 return fmt.Errorf("expected a goroutine but didn't have one")
 733         } else if reqs.Goroutine == event.MustNotHave && ctx.G != NoGoroutine {
 734                 return fmt.Errorf("expected no goroutine but had one")
 735         }
 736         return nil
 737 }
 738
 739 // gcState is a trinary variable for the current state of the GC.
 740 //
 741 // The third state besides "enabled" and "disabled" is "undetermined."
 742 type gcState uint8
 743
 744 const (
 745         gcUndetermined gcState = iota
 746         gcNotRunning
 747         gcRunning
 748 )
 749
 750 // String returns a human-readable string for the GC state.
 751 func (s gcState) String() string {
 752         switch s {
 753         case gcUndetermined:
 754                 return "Undetermined"
 755         case gcNotRunning:
 756                 return "NotRunning"
 757         case gcRunning:
 758                 return "Running"
 759         }
 760         return "Bad"
 761 }
 762
 763 // userRegion represents a unique user region when attached to some gState.
 764 type userRegion struct {
 765         // name must be a resolved string because the string ID for the same
 766         // string may change across generations, but we care about checking
 767         // the value itself.
 768         taskID TaskID
 769         name   string
 770 }
 771
 772 // rangeType is a way to classify special ranges of time.
 773 //
 774 // These typically correspond 1:1 with "Begin" events, but
 775 // they may have an optional subtype that describes the range
 776 // in more detail.
 777 type rangeType struct {
 778         typ  event.Type // "Begin" event.
 779         desc stringID   // Optional subtype.
 780 }
 781
 782 // makeRangeType constructs a new rangeType.
 783 func makeRangeType(typ event.Type, desc stringID) rangeType {
 784         if styp := go122.Specs()[typ].StartEv; styp != go122.EvNone {
 785                 typ = styp
 786         }
 787         return rangeType{typ, desc}
 788 }
 789
 790 // gState is the state of a goroutine at a point in the trace.
 791 type gState struct {
 792         id     GoID
 793         status go122.GoStatus
 794         seq    seqCounter
 795
 796         // regions are the active user regions for this goroutine.
 797         regions []userRegion
 798
 799         // rangeState is the state of special time ranges bound to this goroutine.
 800         rangeState
 801 }
 802
 803 // beginRegion starts a user region on the goroutine.
 804 func (s *gState) beginRegion(r userRegion) error {
 805         s.regions = append(s.regions, r)
 806         return nil
 807 }
 808
 809 // endRegion ends a user region on the goroutine.
 810 func (s *gState) endRegion(r userRegion) error {
 811         if next := s.regions[len(s.regions)-1]; next != r {
 812                 return fmt.Errorf("misuse of region in goroutine %v: region end %v when the inner-most active region start event is %v", s.id, r, next)
 813         }
 814         s.regions = s.regions[:len(s.regions)-1]
 815         return nil
 816 }
 817
 818 // pState is the state of a proc at a point in the trace.
 819 type pState struct {
 820         id     ProcID
 821         status go122.ProcStatus
 822         seq    seqCounter
 823
 824         // rangeState is the state of special time ranges bound to this proc.
 825         rangeState
 826 }
 827
 828 // mState is the state of a thread at a point in the trace.
 829 type mState struct {
 830         g GoID   // Goroutine bound to this M. (The goroutine's state is Executing.)
 831         p ProcID // Proc bound to this M. (The proc's state is Executing.)
 832 }
 833
 834 // rangeState represents the state of special time ranges.
 835 type rangeState struct {
 836         // inFlight contains the rangeTypes of any ranges bound to a resource.
 837         inFlight []rangeType
 838 }
 839
 840 // beginRange begins a special range in time on the goroutine.
 841 //
 842 // Returns an error if the range is already in progress.
 843 func (s *rangeState) beginRange(typ rangeType) error {
 844         if s.hasRange(typ) {
 845                 return fmt.Errorf("discovered event already in-flight for when starting event %v", go122.Specs()[typ.typ].Name)
 846         }
 847         s.inFlight = append(s.inFlight, typ)
 848         return nil
 849 }
 850
 851 // activeRange marks special range in time on the goroutine as active in the
 852 // initial generation, or confirms that it is indeed active in later generations.
 853 func (s *rangeState) activeRange(typ rangeType, isInitialGen bool) error {
 854         if isInitialGen {
 855                 if s.hasRange(typ) {
 856                         return fmt.Errorf("found named active range already in first gen: %v", typ)
 857                 }
 858                 s.inFlight = append(s.inFlight, typ)
 859         } else if !s.hasRange(typ) {
 860                 return fmt.Errorf("resource is missing active range: %v %v", go122.Specs()[typ.typ].Name, s.inFlight)
 861         }
 862         return nil
 863 }
 864
 865 // hasRange returns true if a special time range on the goroutine as in progress.
 866 func (s *rangeState) hasRange(typ rangeType) bool {
 867         for _, ftyp := range s.inFlight {
 868                 if ftyp == typ {
 869                         return true
 870                 }
 871         }
 872         return false
 873 }
 874
 875 // endsRange ends a special range in time on the goroutine.
 876 //
 877 // This must line up with the start event type  of the range the goroutine is currently in.
 878 func (s *rangeState) endRange(typ event.Type) (stringID, error) {
 879         st := go122.Specs()[typ].StartEv
 880         idx := -1
 881         for i, r := range s.inFlight {
 882                 if r.typ == st {
 883                         idx = i
 884                         break
 885                 }
 886         }
 887         if idx < 0 {
 888                 return 0, fmt.Errorf("tried to end event %v, but not in-flight", go122.Specs()[st].Name)
 889         }
 890         // Swap remove.
 891         desc := s.inFlight[idx].desc
 892         s.inFlight[idx], s.inFlight[len(s.inFlight)-1] = s.inFlight[len(s.inFlight)-1], s.inFlight[idx]
 893         s.inFlight = s.inFlight[:len(s.inFlight)-1]
 894         return desc, nil
 895 }
 896
 897 // seqCounter represents a global sequence counter for a resource.
 898 type seqCounter struct {
 899         gen uint64 // The generation for the local sequence counter seq.
 900         seq uint64 // The sequence number local to the generation.
 901 }
 902
 903 // makeSeq creates a new seqCounter.
 904 func makeSeq(gen, seq uint64) seqCounter {
 905         return seqCounter{gen: gen, seq: seq}
 906 }
 907
 908 // succeeds returns true if a is the immediate successor of b.
 909 func (a seqCounter) succeeds(b seqCounter) bool {
 910         return a.gen == b.gen && a.seq == b.seq+1
 911 }
 912
 913 // String returns a debug string representation of the seqCounter.
 914 func (c seqCounter) String() string {
 915         return fmt.Sprintf("%d (gen=%d)", c.seq, c.gen)
 916 }
 917
 918 func dumpOrdering(order *ordering) string {
 919         var sb strings.Builder
 920         for id, state := range order.gStates {
 921                 fmt.Fprintf(&sb, "G %d [status=%s seq=%s]\n", id, state.status, state.seq)
 922         }
 923         fmt.Fprintln(&sb)
 924         for id, state := range order.pStates {
 925                 fmt.Fprintf(&sb, "P %d [status=%s seq=%s]\n", id, state.status, state.seq)
 926         }
 927         fmt.Fprintln(&sb)
 928         for id, state := range order.mStates {
 929                 fmt.Fprintf(&sb, "M %d [g=%d p=%d]\n", id, state.g, state.p)
 930         }
 931         fmt.Fprintln(&sb)
 932         fmt.Fprintf(&sb, "GC %d %s\n", order.gcSeq, order.gcState)
 933         return sb.String()
 934 }
 935
 936 // taskState represents an active task.
 937 type taskState struct {
 938         // name is the type of the active task.
 939         name string
 940
 941         // parentID is the parent ID of the active task.
 942         parentID TaskID
 943 }