Source file src/golang.org/x/exp/trace/order.go

Documentation: golang.org/x/exp/trace

     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  // Code generated by "gen.bash" from internal/trace/v2; DO NOT EDIT.
     6  
     7  //go:build go1.21
     8  
     9  package trace
    10  
    11  import (
    12  	"fmt"
    13  	"strings"
    14  
    15  	"golang.org/x/exp/trace/internal/event"
    16  	"golang.org/x/exp/trace/internal/event/go122"
    17  	"golang.org/x/exp/trace/internal/version"
    18  )
    19  
    20  // ordering emulates Go scheduler state for both validation and
    21  // for putting events in the right order.
    22  //
    23  // The interface to ordering consists of two methods: Advance
    24  // and Next. Advance is called to try and advance an event and
    25  // add completed events to the ordering. Next is used to pick
    26  // off events in the ordering.
    27  type ordering struct {
    28  	gStates     map[GoID]*gState
    29  	pStates     map[ProcID]*pState // TODO: The keys are dense, so this can be a slice.
    30  	mStates     map[ThreadID]*mState
    31  	activeTasks map[TaskID]taskState
    32  	gcSeq       uint64
    33  	gcState     gcState
    34  	initialGen  uint64
    35  	queue       queue[Event]
    36  }
    37  
    38  // Advance checks if it's valid to proceed with ev which came from thread m.
    39  //
    40  // It assumes the gen value passed to it is monotonically increasing across calls.
    41  //
    42  // If any error is returned, then the trace is broken and trace parsing must cease.
    43  // If it's not valid to advance with ev, but no error was encountered, the caller
    44  // should attempt to advance with other candidate events from other threads. If the
    45  // caller runs out of candidates, the trace is invalid.
    46  //
    47  // If this returns true, Next is guaranteed to return a complete event. However,
    48  // multiple events may be added to the ordering, so the caller should (but is not
    49  // required to) continue to call Next until it is exhausted.
    50  func (o *ordering) Advance(ev *baseEvent, evt *evTable, m ThreadID, gen uint64) (bool, error) {
    51  	if o.initialGen == 0 {
    52  		// Set the initial gen if necessary.
    53  		o.initialGen = gen
    54  	}
    55  
    56  	var curCtx, newCtx schedCtx
    57  	curCtx.M = m
    58  	newCtx.M = m
    59  
    60  	var ms *mState
    61  	if m == NoThread {
    62  		curCtx.P = NoProc
    63  		curCtx.G = NoGoroutine
    64  		newCtx = curCtx
    65  	} else {
    66  		// Pull out or create the mState for this event.
    67  		var ok bool
    68  		ms, ok = o.mStates[m]
    69  		if !ok {
    70  			ms = &mState{
    71  				g: NoGoroutine,
    72  				p: NoProc,
    73  			}
    74  			o.mStates[m] = ms
    75  		}
    76  		curCtx.P = ms.p
    77  		curCtx.G = ms.g
    78  		newCtx = curCtx
    79  	}
    80  
    81  	f := orderingDispatch[ev.typ]
    82  	if f == nil {
    83  		return false, fmt.Errorf("bad event type found while ordering: %v", ev.typ)
    84  	}
    85  	newCtx, ok, err := f(o, ev, evt, m, gen, curCtx)
    86  	if err == nil && ok && ms != nil {
    87  		// Update the mState for this event.
    88  		ms.p = newCtx.P
    89  		ms.g = newCtx.G
    90  	}
    91  	return ok, err
    92  }
    93  
    94  type orderingHandleFunc func(o *ordering, ev *baseEvent, evt *evTable, m ThreadID, gen uint64, curCtx schedCtx) (schedCtx, bool, error)
    95  
    96  var orderingDispatch = [256]orderingHandleFunc{
    97  	// Procs.
    98  	go122.EvProcsChange: (*ordering).advanceAnnotation,
    99  	go122.EvProcStart:   (*ordering).advanceProcStart,
   100  	go122.EvProcStop:    (*ordering).advanceProcStop,
   101  	go122.EvProcSteal:   (*ordering).advanceProcSteal,
   102  	go122.EvProcStatus:  (*ordering).advanceProcStatus,
   103  
   104  	// Goroutines.
   105  	go122.EvGoCreate:            (*ordering).advanceGoCreate,
   106  	go122.EvGoCreateSyscall:     (*ordering).advanceGoCreateSyscall,
   107  	go122.EvGoStart:             (*ordering).advanceGoStart,
   108  	go122.EvGoDestroy:           (*ordering).advanceGoStopExec,
   109  	go122.EvGoDestroySyscall:    (*ordering).advanceGoDestroySyscall,
   110  	go122.EvGoStop:              (*ordering).advanceGoStopExec,
   111  	go122.EvGoBlock:             (*ordering).advanceGoStopExec,
   112  	go122.EvGoUnblock:           (*ordering).advanceGoUnblock,
   113  	go122.EvGoSyscallBegin:      (*ordering).advanceGoSyscallBegin,
   114  	go122.EvGoSyscallEnd:        (*ordering).advanceGoSyscallEnd,
   115  	go122.EvGoSyscallEndBlocked: (*ordering).advanceGoSyscallEndBlocked,
   116  	go122.EvGoStatus:            (*ordering).advanceGoStatus,
   117  
   118  	// STW.
   119  	go122.EvSTWBegin: (*ordering).advanceGoRangeBegin,
   120  	go122.EvSTWEnd:   (*ordering).advanceGoRangeEnd,
   121  
   122  	// GC events.
   123  	go122.EvGCActive:           (*ordering).advanceGCActive,
   124  	go122.EvGCBegin:            (*ordering).advanceGCBegin,
   125  	go122.EvGCEnd:              (*ordering).advanceGCEnd,
   126  	go122.EvGCSweepActive:      (*ordering).advanceGCSweepActive,
   127  	go122.EvGCSweepBegin:       (*ordering).advanceGCSweepBegin,
   128  	go122.EvGCSweepEnd:         (*ordering).advanceGCSweepEnd,
   129  	go122.EvGCMarkAssistActive: (*ordering).advanceGoRangeActive,
   130  	go122.EvGCMarkAssistBegin:  (*ordering).advanceGoRangeBegin,
   131  	go122.EvGCMarkAssistEnd:    (*ordering).advanceGoRangeEnd,
   132  	go122.EvHeapAlloc:          (*ordering).advanceHeapMetric,
   133  	go122.EvHeapGoal:           (*ordering).advanceHeapMetric,
   134  
   135  	// Annotations.
   136  	go122.EvGoLabel:         (*ordering).advanceAnnotation,
   137  	go122.EvUserTaskBegin:   (*ordering).advanceUserTaskBegin,
   138  	go122.EvUserTaskEnd:     (*ordering).advanceUserTaskEnd,
   139  	go122.EvUserRegionBegin: (*ordering).advanceUserRegionBegin,
   140  	go122.EvUserRegionEnd:   (*ordering).advanceUserRegionEnd,
   141  	go122.EvUserLog:         (*ordering).advanceAnnotation,
   142  
   143  	// Coroutines. Added in Go 1.23.
   144  	go122.EvGoSwitch:        (*ordering).advanceGoSwitch,
   145  	go122.EvGoSwitchDestroy: (*ordering).advanceGoSwitch,
   146  	go122.EvGoCreateBlocked: (*ordering).advanceGoCreate,
   147  
   148  	// GoStatus event with a stack. Added in Go 1.23.
   149  	go122.EvGoStatusStack: (*ordering).advanceGoStatus,
   150  }
   151  
   152  func (o *ordering) advanceProcStatus(ev *baseEvent, evt *evTable, m ThreadID, gen uint64, curCtx schedCtx) (schedCtx, bool, error) {
   153  	pid := ProcID(ev.args[0])
   154  	status := go122.ProcStatus(ev.args[1])
   155  	if int(status) >= len(go122ProcStatus2ProcState) {
   156  		return curCtx, false, fmt.Errorf("invalid status for proc %d: %d", pid, status)
   157  	}
   158  	oldState := go122ProcStatus2ProcState[status]
   159  	if s, ok := o.pStates[pid]; ok {
   160  		if status == go122.ProcSyscallAbandoned && s.status == go122.ProcSyscall {
   161  			// ProcSyscallAbandoned is a special case of ProcSyscall. It indicates a
   162  			// potential loss of information, but if we're already in ProcSyscall,
   163  			// we haven't lost the relevant information. Promote the status and advance.
   164  			oldState = ProcRunning
   165  			ev.args[1] = uint64(go122.ProcSyscall)
   166  		} else if status == go122.ProcSyscallAbandoned && s.status == go122.ProcSyscallAbandoned {
   167  			// If we're passing through ProcSyscallAbandoned, then there's no promotion
   168  			// to do. We've lost the M that this P is associated with. However it got there,
   169  			// it's going to appear as idle in the API, so pass through as idle.
   170  			oldState = ProcIdle
   171  			ev.args[1] = uint64(go122.ProcSyscallAbandoned)
   172  		} else if s.status != status {
   173  			return curCtx, false, fmt.Errorf("inconsistent status for proc %d: old %v vs. new %v", pid, s.status, status)
   174  		}
   175  		s.seq = makeSeq(gen, 0) // Reset seq.
   176  	} else {
   177  		o.pStates[pid] = &pState{id: pid, status: status, seq: makeSeq(gen, 0)}
   178  		if gen == o.initialGen {
   179  			oldState = ProcUndetermined
   180  		} else {
   181  			oldState = ProcNotExist
   182  		}
   183  	}
   184  	ev.extra(version.Go122)[0] = uint64(oldState) // Smuggle in the old state for StateTransition.
   185  
   186  	// Bind the proc to the new context, if it's running.
   187  	newCtx := curCtx
   188  	if status == go122.ProcRunning || status == go122.ProcSyscall {
   189  		newCtx.P = pid
   190  	}
   191  	// If we're advancing through ProcSyscallAbandoned *but* oldState is running then we've
   192  	// promoted it to ProcSyscall. However, because it's ProcSyscallAbandoned, we know this
   193  	// P is about to get stolen and its status very likely isn't being emitted by the same
   194  	// thread it was bound to. Since this status is Running -> Running and Running is binding,
   195  	// we need to make sure we emit it in the right context: the context to which it is bound.
   196  	// Find it, and set our current context to it.
   197  	if status == go122.ProcSyscallAbandoned && oldState == ProcRunning {
   198  		// N.B. This is slow but it should be fairly rare.
   199  		found := false
   200  		for mid, ms := range o.mStates {
   201  			if ms.p == pid {
   202  				curCtx.M = mid
   203  				curCtx.P = pid
   204  				curCtx.G = ms.g
   205  				found = true
   206  			}
   207  		}
   208  		if !found {
   209  			return curCtx, false, fmt.Errorf("failed to find sched context for proc %d that's about to be stolen", pid)
   210  		}
   211  	}
   212  	o.queue.push(Event{table: evt, ctx: curCtx, base: *ev})
   213  	return newCtx, true, nil
   214  }
   215  
   216  func (o *ordering) advanceProcStart(ev *baseEvent, evt *evTable, m ThreadID, gen uint64, curCtx schedCtx) (schedCtx, bool, error) {
   217  	pid := ProcID(ev.args[0])
   218  	seq := makeSeq(gen, ev.args[1])
   219  
   220  	// Try to advance. We might fail here due to sequencing, because the P hasn't
   221  	// had a status emitted, or because we already have a P and we're in a syscall,
   222  	// and we haven't observed that it was stolen from us yet.
   223  	state, ok := o.pStates[pid]
   224  	if !ok || state.status != go122.ProcIdle || !seq.succeeds(state.seq) || curCtx.P != NoProc {
   225  		// We can't make an inference as to whether this is bad. We could just be seeing
   226  		// a ProcStart on a different M before the proc's state was emitted, or before we
   227  		// got to the right point in the trace.
   228  		//
   229  		// Note that we also don't advance here if we have a P and we're in a syscall.
   230  		return curCtx, false, nil
   231  	}
   232  	// We can advance this P. Check some invariants.
   233  	//
   234  	// We might have a goroutine if a goroutine is exiting a syscall.
   235  	reqs := event.SchedReqs{Thread: event.MustHave, Proc: event.MustNotHave, Goroutine: event.MayHave}
   236  	if err := validateCtx(curCtx, reqs); err != nil {
   237  		return curCtx, false, err
   238  	}
   239  	state.status = go122.ProcRunning
   240  	state.seq = seq
   241  	newCtx := curCtx
   242  	newCtx.P = pid
   243  	o.queue.push(Event{table: evt, ctx: curCtx, base: *ev})
   244  	return newCtx, true, nil
   245  }
   246  
   247  func (o *ordering) advanceProcStop(ev *baseEvent, evt *evTable, m ThreadID, gen uint64, curCtx schedCtx) (schedCtx, bool, error) {
   248  	// We must be able to advance this P.
   249  	//
   250  	// There are 2 ways a P can stop: ProcStop and ProcSteal. ProcStop is used when the P
   251  	// is stopped by the same M that started it, while ProcSteal is used when another M
   252  	// steals the P by stopping it from a distance.
   253  	//
   254  	// Since a P is bound to an M, and we're stopping on the same M we started, it must
   255  	// always be possible to advance the current M's P from a ProcStop. This is also why
   256  	// ProcStop doesn't need a sequence number.
   257  	state, ok := o.pStates[curCtx.P]
   258  	if !ok {
   259  		return curCtx, false, fmt.Errorf("event %s for proc (%v) that doesn't exist", go122.EventString(ev.typ), curCtx.P)
   260  	}
   261  	if state.status != go122.ProcRunning && state.status != go122.ProcSyscall {
   262  		return curCtx, false, fmt.Errorf("%s event for proc that's not %s or %s", go122.EventString(ev.typ), go122.ProcRunning, go122.ProcSyscall)
   263  	}
   264  	reqs := event.SchedReqs{Thread: event.MustHave, Proc: event.MustHave, Goroutine: event.MayHave}
   265  	if err := validateCtx(curCtx, reqs); err != nil {
   266  		return curCtx, false, err
   267  	}
   268  	state.status = go122.ProcIdle
   269  	newCtx := curCtx
   270  	newCtx.P = NoProc
   271  	o.queue.push(Event{table: evt, ctx: curCtx, base: *ev})
   272  	return newCtx, true, nil
   273  }
   274  
   275  func (o *ordering) advanceProcSteal(ev *baseEvent, evt *evTable, m ThreadID, gen uint64, curCtx schedCtx) (schedCtx, bool, error) {
   276  	pid := ProcID(ev.args[0])
   277  	seq := makeSeq(gen, ev.args[1])
   278  	state, ok := o.pStates[pid]
   279  	if !ok || (state.status != go122.ProcSyscall && state.status != go122.ProcSyscallAbandoned) || !seq.succeeds(state.seq) {
   280  		// We can't make an inference as to whether this is bad. We could just be seeing
   281  		// a ProcStart on a different M before the proc's state was emitted, or before we
   282  		// got to the right point in the trace.
   283  		return curCtx, false, nil
   284  	}
   285  	// We can advance this P. Check some invariants.
   286  	reqs := event.SchedReqs{Thread: event.MustHave, Proc: event.MayHave, Goroutine: event.MayHave}
   287  	if err := validateCtx(curCtx, reqs); err != nil {
   288  		return curCtx, false, err
   289  	}
   290  	// Smuggle in the P state that let us advance so we can surface information to the event.
   291  	// Specifically, we need to make sure that the event is interpreted not as a transition of
   292  	// ProcRunning -> ProcIdle but ProcIdle -> ProcIdle instead.
   293  	//
   294  	// ProcRunning is binding, but we may be running with a P on the current M and we can't
   295  	// bind another P. This P is about to go ProcIdle anyway.
   296  	oldStatus := state.status
   297  	ev.extra(version.Go122)[0] = uint64(oldStatus)
   298  
   299  	// Update the P's status and sequence number.
   300  	state.status = go122.ProcIdle
   301  	state.seq = seq
   302  
   303  	// If we've lost information then don't try to do anything with the M.
   304  	// It may have moved on and we can't be sure.
   305  	if oldStatus == go122.ProcSyscallAbandoned {
   306  		o.queue.push(Event{table: evt, ctx: curCtx, base: *ev})
   307  		return curCtx, true, nil
   308  	}
   309  
   310  	// Validate that the M we're stealing from is what we expect.
   311  	mid := ThreadID(ev.args[2]) // The M we're stealing from.
   312  
   313  	newCtx := curCtx
   314  	if mid == curCtx.M {
   315  		// We're stealing from ourselves. This behaves like a ProcStop.
   316  		if curCtx.P != pid {
   317  			return curCtx, false, fmt.Errorf("tried to self-steal proc %d (thread %d), but got proc %d instead", pid, mid, curCtx.P)
   318  		}
   319  		newCtx.P = NoProc
   320  		o.queue.push(Event{table: evt, ctx: curCtx, base: *ev})
   321  		return newCtx, true, nil
   322  	}
   323  
   324  	// We're stealing from some other M.
   325  	mState, ok := o.mStates[mid]
   326  	if !ok {
   327  		return curCtx, false, fmt.Errorf("stole proc from non-existent thread %d", mid)
   328  	}
   329  
   330  	// Make sure we're actually stealing the right P.
   331  	if mState.p != pid {
   332  		return curCtx, false, fmt.Errorf("tried to steal proc %d from thread %d, but got proc %d instead", pid, mid, mState.p)
   333  	}
   334  
   335  	// Tell the M it has no P so it can proceed.
   336  	//
   337  	// This is safe because we know the P was in a syscall and
   338  	// the other M must be trying to get out of the syscall.
   339  	// GoSyscallEndBlocked cannot advance until the corresponding
   340  	// M loses its P.
   341  	mState.p = NoProc
   342  	o.queue.push(Event{table: evt, ctx: curCtx, base: *ev})
   343  	return newCtx, true, nil
   344  }
   345  
   346  func (o *ordering) advanceGoStatus(ev *baseEvent, evt *evTable, m ThreadID, gen uint64, curCtx schedCtx) (schedCtx, bool, error) {
   347  	gid := GoID(ev.args[0])
   348  	mid := ThreadID(ev.args[1])
   349  	status := go122.GoStatus(ev.args[2])
   350  
   351  	if int(status) >= len(go122GoStatus2GoState) {
   352  		return curCtx, false, fmt.Errorf("invalid status for goroutine %d: %d", gid, status)
   353  	}
   354  	oldState := go122GoStatus2GoState[status]
   355  	if s, ok := o.gStates[gid]; ok {
   356  		if s.status != status {
   357  			return curCtx, false, fmt.Errorf("inconsistent status for goroutine %d: old %v vs. new %v", gid, s.status, status)
   358  		}
   359  		s.seq = makeSeq(gen, 0) // Reset seq.
   360  	} else if gen == o.initialGen {
   361  		// Set the state.
   362  		o.gStates[gid] = &gState{id: gid, status: status, seq: makeSeq(gen, 0)}
   363  		oldState = GoUndetermined
   364  	} else {
   365  		return curCtx, false, fmt.Errorf("found goroutine status for new goroutine after the first generation: id=%v status=%v", gid, status)
   366  	}
   367  	ev.extra(version.Go122)[0] = uint64(oldState) // Smuggle in the old state for StateTransition.
   368  
   369  	newCtx := curCtx
   370  	switch status {
   371  	case go122.GoRunning:
   372  		// Bind the goroutine to the new context, since it's running.
   373  		newCtx.G = gid
   374  	case go122.GoSyscall:
   375  		if mid == NoThread {
   376  			return curCtx, false, fmt.Errorf("found goroutine %d in syscall without a thread", gid)
   377  		}
   378  		// Is the syscall on this thread? If so, bind it to the context.
   379  		// Otherwise, we're talking about a G sitting in a syscall on an M.
   380  		// Validate the named M.
   381  		if mid == curCtx.M {
   382  			if gen != o.initialGen && curCtx.G != gid {
   383  				// If this isn't the first generation, we *must* have seen this
   384  				// binding occur already. Even if the G was blocked in a syscall
   385  				// for multiple generations since trace start, we would have seen
   386  				// a previous GoStatus event that bound the goroutine to an M.
   387  				return curCtx, false, fmt.Errorf("inconsistent thread for syscalling goroutine %d: thread has goroutine %d", gid, curCtx.G)
   388  			}
   389  			newCtx.G = gid
   390  			break
   391  		}
   392  		// Now we're talking about a thread and goroutine that have been
   393  		// blocked on a syscall for the entire generation. This case must
   394  		// not have a P; the runtime makes sure that all Ps are traced at
   395  		// the beginning of a generation, which involves taking a P back
   396  		// from every thread.
   397  		ms, ok := o.mStates[mid]
   398  		if ok {
   399  			// This M has been seen. That means we must have seen this
   400  			// goroutine go into a syscall on this thread at some point.
   401  			if ms.g != gid {
   402  				// But the G on the M doesn't match. Something's wrong.
   403  				return curCtx, false, fmt.Errorf("inconsistent thread for syscalling goroutine %d: thread has goroutine %d", gid, ms.g)
   404  			}
   405  			// This case is just a Syscall->Syscall event, which needs to
   406  			// appear as having the G currently bound to this M.
   407  			curCtx.G = ms.g
   408  		} else if !ok {
   409  			// The M hasn't been seen yet. That means this goroutine
   410  			// has just been sitting in a syscall on this M. Create
   411  			// a state for it.
   412  			o.mStates[mid] = &mState{g: gid, p: NoProc}
   413  			// Don't set curCtx.G in this case because this event is the
   414  			// binding event (and curCtx represents the "before" state).
   415  		}
   416  		// Update the current context to the M we're talking about.
   417  		curCtx.M = mid
   418  	}
   419  	o.queue.push(Event{table: evt, ctx: curCtx, base: *ev})
   420  	return newCtx, true, nil
   421  }
   422  
   423  func (o *ordering) advanceGoCreate(ev *baseEvent, evt *evTable, m ThreadID, gen uint64, curCtx schedCtx) (schedCtx, bool, error) {
   424  	// Goroutines must be created on a running P, but may or may not be created
   425  	// by a running goroutine.
   426  	reqs := event.SchedReqs{Thread: event.MustHave, Proc: event.MustHave, Goroutine: event.MayHave}
   427  	if err := validateCtx(curCtx, reqs); err != nil {
   428  		return curCtx, false, err
   429  	}
   430  	// If we have a goroutine, it must be running.
   431  	if state, ok := o.gStates[curCtx.G]; ok && state.status != go122.GoRunning {
   432  		return curCtx, false, fmt.Errorf("%s event for goroutine that's not %s", go122.EventString(ev.typ), GoRunning)
   433  	}
   434  	// This goroutine created another. Add a state for it.
   435  	newgid := GoID(ev.args[0])
   436  	if _, ok := o.gStates[newgid]; ok {
   437  		return curCtx, false, fmt.Errorf("tried to create goroutine (%v) that already exists", newgid)
   438  	}
   439  	status := go122.GoRunnable
   440  	if ev.typ == go122.EvGoCreateBlocked {
   441  		status = go122.GoWaiting
   442  	}
   443  	o.gStates[newgid] = &gState{id: newgid, status: status, seq: makeSeq(gen, 0)}
   444  	o.queue.push(Event{table: evt, ctx: curCtx, base: *ev})
   445  	return curCtx, true, nil
   446  }
   447  
   448  func (o *ordering) advanceGoStopExec(ev *baseEvent, evt *evTable, m ThreadID, gen uint64, curCtx schedCtx) (schedCtx, bool, error) {
   449  	// These are goroutine events that all require an active running
   450  	// goroutine on some thread. They must *always* be advance-able,
   451  	// since running goroutines are bound to their M.
   452  	if err := validateCtx(curCtx, event.UserGoReqs); err != nil {
   453  		return curCtx, false, err
   454  	}
   455  	state, ok := o.gStates[curCtx.G]
   456  	if !ok {
   457  		return curCtx, false, fmt.Errorf("event %s for goroutine (%v) that doesn't exist", go122.EventString(ev.typ), curCtx.G)
   458  	}
   459  	if state.status != go122.GoRunning {
   460  		return curCtx, false, fmt.Errorf("%s event for goroutine that's not %s", go122.EventString(ev.typ), GoRunning)
   461  	}
   462  	// Handle each case slightly differently; we just group them together
   463  	// because they have shared preconditions.
   464  	newCtx := curCtx
   465  	switch ev.typ {
   466  	case go122.EvGoDestroy:
   467  		// This goroutine is exiting itself.
   468  		delete(o.gStates, curCtx.G)
   469  		newCtx.G = NoGoroutine
   470  	case go122.EvGoStop:
   471  		// Goroutine stopped (yielded). It's runnable but not running on this M.
   472  		state.status = go122.GoRunnable
   473  		newCtx.G = NoGoroutine
   474  	case go122.EvGoBlock:
   475  		// Goroutine blocked. It's waiting now and not running on this M.
   476  		state.status = go122.GoWaiting
   477  		newCtx.G = NoGoroutine
   478  	}
   479  	o.queue.push(Event{table: evt, ctx: curCtx, base: *ev})
   480  	return newCtx, true, nil
   481  }
   482  
   483  func (o *ordering) advanceGoStart(ev *baseEvent, evt *evTable, m ThreadID, gen uint64, curCtx schedCtx) (schedCtx, bool, error) {
   484  	gid := GoID(ev.args[0])
   485  	seq := makeSeq(gen, ev.args[1])
   486  	state, ok := o.gStates[gid]
   487  	if !ok || state.status != go122.GoRunnable || !seq.succeeds(state.seq) {
   488  		// We can't make an inference as to whether this is bad. We could just be seeing
   489  		// a GoStart on a different M before the goroutine was created, before it had its
   490  		// state emitted, or before we got to the right point in the trace yet.
   491  		return curCtx, false, nil
   492  	}
   493  	// We can advance this goroutine. Check some invariants.
   494  	reqs := event.SchedReqs{Thread: event.MustHave, Proc: event.MustHave, Goroutine: event.MustNotHave}
   495  	if err := validateCtx(curCtx, reqs); err != nil {
   496  		return curCtx, false, err
   497  	}
   498  	state.status = go122.GoRunning
   499  	state.seq = seq
   500  	newCtx := curCtx
   501  	newCtx.G = gid
   502  	o.queue.push(Event{table: evt, ctx: curCtx, base: *ev})
   503  	return newCtx, true, nil
   504  }
   505  
   506  func (o *ordering) advanceGoUnblock(ev *baseEvent, evt *evTable, m ThreadID, gen uint64, curCtx schedCtx) (schedCtx, bool, error) {
   507  	// N.B. These both reference the goroutine to unblock, not the current goroutine.
   508  	gid := GoID(ev.args[0])
   509  	seq := makeSeq(gen, ev.args[1])
   510  	state, ok := o.gStates[gid]
   511  	if !ok || state.status != go122.GoWaiting || !seq.succeeds(state.seq) {
   512  		// We can't make an inference as to whether this is bad. We could just be seeing
   513  		// a GoUnblock on a different M before the goroutine was created and blocked itself,
   514  		// before it had its state emitted, or before we got to the right point in the trace yet.
   515  		return curCtx, false, nil
   516  	}
   517  	state.status = go122.GoRunnable
   518  	state.seq = seq
   519  	// N.B. No context to validate. Basically anything can unblock
   520  	// a goroutine (e.g. sysmon).
   521  	o.queue.push(Event{table: evt, ctx: curCtx, base: *ev})
   522  	return curCtx, true, nil
   523  }
   524  
   525  func (o *ordering) advanceGoSwitch(ev *baseEvent, evt *evTable, m ThreadID, gen uint64, curCtx schedCtx) (schedCtx, bool, error) {
   526  	// GoSwitch and GoSwitchDestroy represent a trio of events:
   527  	// - Unblock of the goroutine to switch to.
   528  	// - Block or destroy of the current goroutine.
   529  	// - Start executing the next goroutine.
   530  	//
   531  	// Because it acts like a GoStart for the next goroutine, we can
   532  	// only advance it if the sequence numbers line up.
   533  	//
   534  	// The current goroutine on the thread must be actively running.
   535  	if err := validateCtx(curCtx, event.UserGoReqs); err != nil {
   536  		return curCtx, false, err
   537  	}
   538  	curGState, ok := o.gStates[curCtx.G]
   539  	if !ok {
   540  		return curCtx, false, fmt.Errorf("event %s for goroutine (%v) that doesn't exist", go122.EventString(ev.typ), curCtx.G)
   541  	}
   542  	if curGState.status != go122.GoRunning {
   543  		return curCtx, false, fmt.Errorf("%s event for goroutine that's not %s", go122.EventString(ev.typ), GoRunning)
   544  	}
   545  	nextg := GoID(ev.args[0])
   546  	seq := makeSeq(gen, ev.args[1]) // seq is for nextg, not curCtx.G.
   547  	nextGState, ok := o.gStates[nextg]
   548  	if !ok || nextGState.status != go122.GoWaiting || !seq.succeeds(nextGState.seq) {
   549  		// We can't make an inference as to whether this is bad. We could just be seeing
   550  		// a GoSwitch on a different M before the goroutine was created, before it had its
   551  		// state emitted, or before we got to the right point in the trace yet.
   552  		return curCtx, false, nil
   553  	}
   554  	o.queue.push(Event{table: evt, ctx: curCtx, base: *ev})
   555  
   556  	// Update the state of the executing goroutine and emit an event for it
   557  	// (GoSwitch and GoSwitchDestroy will be interpreted as GoUnblock events
   558  	// for nextg).
   559  	switch ev.typ {
   560  	case go122.EvGoSwitch:
   561  		// Goroutine blocked. It's waiting now and not running on this M.
   562  		curGState.status = go122.GoWaiting
   563  
   564  		// Emit a GoBlock event.
   565  		// TODO(mknyszek): Emit a reason.
   566  		o.queue.push(makeEvent(evt, curCtx, go122.EvGoBlock, ev.time, 0 /* no reason */, 0 /* no stack */))
   567  	case go122.EvGoSwitchDestroy:
   568  		// This goroutine is exiting itself.
   569  		delete(o.gStates, curCtx.G)
   570  
   571  		// Emit a GoDestroy event.
   572  		o.queue.push(makeEvent(evt, curCtx, go122.EvGoDestroy, ev.time))
   573  	}
   574  	// Update the state of the next goroutine.
   575  	nextGState.status = go122.GoRunning
   576  	nextGState.seq = seq
   577  	newCtx := curCtx
   578  	newCtx.G = nextg
   579  
   580  	// Queue an event for the next goroutine starting to run.
   581  	startCtx := curCtx
   582  	startCtx.G = NoGoroutine
   583  	o.queue.push(makeEvent(evt, startCtx, go122.EvGoStart, ev.time, uint64(nextg), ev.args[1]))
   584  	return newCtx, true, nil
   585  }
   586  
   587  func (o *ordering) advanceGoSyscallBegin(ev *baseEvent, evt *evTable, m ThreadID, gen uint64, curCtx schedCtx) (schedCtx, bool, error) {
   588  	// Entering a syscall requires an active running goroutine with a
   589  	// proc on some thread. It is always advancable.
   590  	if err := validateCtx(curCtx, event.UserGoReqs); err != nil {
   591  		return curCtx, false, err
   592  	}
   593  	state, ok := o.gStates[curCtx.G]
   594  	if !ok {
   595  		return curCtx, false, fmt.Errorf("event %s for goroutine (%v) that doesn't exist", go122.EventString(ev.typ), curCtx.G)
   596  	}
   597  	if state.status != go122.GoRunning {
   598  		return curCtx, false, fmt.Errorf("%s event for goroutine that's not %s", go122.EventString(ev.typ), GoRunning)
   599  	}
   600  	// Goroutine entered a syscall. It's still running on this P and M.
   601  	state.status = go122.GoSyscall
   602  	pState, ok := o.pStates[curCtx.P]
   603  	if !ok {
   604  		return curCtx, false, fmt.Errorf("uninitialized proc %d found during %s", curCtx.P, go122.EventString(ev.typ))
   605  	}
   606  	pState.status = go122.ProcSyscall
   607  	// Validate the P sequence number on the event and advance it.
   608  	//
   609  	// We have a P sequence number for what is supposed to be a goroutine event
   610  	// so that we can correctly model P stealing. Without this sequence number here,
   611  	// the syscall from which a ProcSteal event is stealing can be ambiguous in the
   612  	// face of broken timestamps. See the go122-syscall-steal-proc-ambiguous test for
   613  	// more details.
   614  	//
   615  	// Note that because this sequence number only exists as a tool for disambiguation,
   616  	// we can enforce that we have the right sequence number at this point; we don't need
   617  	// to back off and see if any other events will advance. This is a running P.
   618  	pSeq := makeSeq(gen, ev.args[0])
   619  	if !pSeq.succeeds(pState.seq) {
   620  		return curCtx, false, fmt.Errorf("failed to advance %s: can't make sequence: %s -> %s", go122.EventString(ev.typ), pState.seq, pSeq)
   621  	}
   622  	pState.seq = pSeq
   623  	o.queue.push(Event{table: evt, ctx: curCtx, base: *ev})
   624  	return curCtx, true, nil
   625  }
   626  
   627  func (o *ordering) advanceGoSyscallEnd(ev *baseEvent, evt *evTable, m ThreadID, gen uint64, curCtx schedCtx) (schedCtx, bool, error) {
   628  	// This event is always advance-able because it happens on the same
   629  	// thread that EvGoSyscallStart happened, and the goroutine can't leave
   630  	// that thread until its done.
   631  	if err := validateCtx(curCtx, event.UserGoReqs); err != nil {
   632  		return curCtx, false, err
   633  	}
   634  	state, ok := o.gStates[curCtx.G]
   635  	if !ok {
   636  		return curCtx, false, fmt.Errorf("event %s for goroutine (%v) that doesn't exist", go122.EventString(ev.typ), curCtx.G)
   637  	}
   638  	if state.status != go122.GoSyscall {
   639  		return curCtx, false, fmt.Errorf("%s event for goroutine that's not %s", go122.EventString(ev.typ), GoRunning)
   640  	}
   641  	state.status = go122.GoRunning
   642  
   643  	// Transfer the P back to running from syscall.
   644  	pState, ok := o.pStates[curCtx.P]
   645  	if !ok {
   646  		return curCtx, false, fmt.Errorf("uninitialized proc %d found during %s", curCtx.P, go122.EventString(ev.typ))
   647  	}
   648  	if pState.status != go122.ProcSyscall {
   649  		return curCtx, false, fmt.Errorf("expected proc %d in state %v, but got %v instead", curCtx.P, go122.ProcSyscall, pState.status)
   650  	}
   651  	pState.status = go122.ProcRunning
   652  	o.queue.push(Event{table: evt, ctx: curCtx, base: *ev})
   653  	return curCtx, true, nil
   654  }
   655  
   656  func (o *ordering) advanceGoSyscallEndBlocked(ev *baseEvent, evt *evTable, m ThreadID, gen uint64, curCtx schedCtx) (schedCtx, bool, error) {
   657  	// This event becomes advanceable when its P is not in a syscall state
   658  	// (lack of a P altogether is also acceptable for advancing).
   659  	// The transfer out of ProcSyscall can happen either voluntarily via
   660  	// ProcStop or involuntarily via ProcSteal. We may also acquire a new P
   661  	// before we get here (after the transfer out) but that's OK: that new
   662  	// P won't be in the ProcSyscall state anymore.
   663  	//
   664  	// Basically: while we have a preemptible P, don't advance, because we
   665  	// *know* from the event that we're going to lose it at some point during
   666  	// the syscall. We shouldn't advance until that happens.
   667  	if curCtx.P != NoProc {
   668  		pState, ok := o.pStates[curCtx.P]
   669  		if !ok {
   670  			return curCtx, false, fmt.Errorf("uninitialized proc %d found during %s", curCtx.P, go122.EventString(ev.typ))
   671  		}
   672  		if pState.status == go122.ProcSyscall {
   673  			return curCtx, false, nil
   674  		}
   675  	}
   676  	// As mentioned above, we may have a P here if we ProcStart
   677  	// before this event.
   678  	if err := validateCtx(curCtx, event.SchedReqs{Thread: event.MustHave, Proc: event.MayHave, Goroutine: event.MustHave}); err != nil {
   679  		return curCtx, false, err
   680  	}
   681  	state, ok := o.gStates[curCtx.G]
   682  	if !ok {
   683  		return curCtx, false, fmt.Errorf("event %s for goroutine (%v) that doesn't exist", go122.EventString(ev.typ), curCtx.G)
   684  	}
   685  	if state.status != go122.GoSyscall {
   686  		return curCtx, false, fmt.Errorf("%s event for goroutine that's not %s", go122.EventString(ev.typ), GoRunning)
   687  	}
   688  	newCtx := curCtx
   689  	newCtx.G = NoGoroutine
   690  	state.status = go122.GoRunnable
   691  	o.queue.push(Event{table: evt, ctx: curCtx, base: *ev})
   692  	return newCtx, true, nil
   693  }
   694  
   695  func (o *ordering) advanceGoCreateSyscall(ev *baseEvent, evt *evTable, m ThreadID, gen uint64, curCtx schedCtx) (schedCtx, bool, error) {
   696  	// This event indicates that a goroutine is effectively
   697  	// being created out of a cgo callback. Such a goroutine
   698  	// is 'created' in the syscall state.
   699  	if err := validateCtx(curCtx, event.SchedReqs{Thread: event.MustHave, Proc: event.MayHave, Goroutine: event.MustNotHave}); err != nil {
   700  		return curCtx, false, err
   701  	}
   702  	// This goroutine is effectively being created. Add a state for it.
   703  	newgid := GoID(ev.args[0])
   704  	if _, ok := o.gStates[newgid]; ok {
   705  		return curCtx, false, fmt.Errorf("tried to create goroutine (%v) in syscall that already exists", newgid)
   706  	}
   707  	o.gStates[newgid] = &gState{id: newgid, status: go122.GoSyscall, seq: makeSeq(gen, 0)}
   708  	// Goroutine is executing. Bind it to the context.
   709  	newCtx := curCtx
   710  	newCtx.G = newgid
   711  	o.queue.push(Event{table: evt, ctx: curCtx, base: *ev})
   712  	return newCtx, true, nil
   713  }
   714  
   715  func (o *ordering) advanceGoDestroySyscall(ev *baseEvent, evt *evTable, m ThreadID, gen uint64, curCtx schedCtx) (schedCtx, bool, error) {
   716  	// This event indicates that a goroutine created for a
   717  	// cgo callback is disappearing, either because the callback
   718  	// ending or the C thread that called it is being destroyed.
   719  	//
   720  	// Also, treat this as if we lost our P too.
   721  	// The thread ID may be reused by the platform and we'll get
   722  	// really confused if we try to steal the P is this is running
   723  	// with later. The new M with the same ID could even try to
   724  	// steal back this P from itself!
   725  	//
   726  	// The runtime is careful to make sure that any GoCreateSyscall
   727  	// event will enter the runtime emitting events for reacquiring a P.
   728  	//
   729  	// Note: we might have a P here. The P might not be released
   730  	// eagerly by the runtime, and it might get stolen back later
   731  	// (or never again, if the program is going to exit).
   732  	if err := validateCtx(curCtx, event.SchedReqs{Thread: event.MustHave, Proc: event.MayHave, Goroutine: event.MustHave}); err != nil {
   733  		return curCtx, false, err
   734  	}
   735  	// Check to make sure the goroutine exists in the right state.
   736  	state, ok := o.gStates[curCtx.G]
   737  	if !ok {
   738  		return curCtx, false, fmt.Errorf("event %s for goroutine (%v) that doesn't exist", go122.EventString(ev.typ), curCtx.G)
   739  	}
   740  	if state.status != go122.GoSyscall {
   741  		return curCtx, false, fmt.Errorf("%s event for goroutine that's not %v", go122.EventString(ev.typ), GoSyscall)
   742  	}
   743  	// This goroutine is exiting itself.
   744  	delete(o.gStates, curCtx.G)
   745  	newCtx := curCtx
   746  	newCtx.G = NoGoroutine
   747  
   748  	// If we have a proc, then we're dissociating from it now. See the comment at the top of the case.
   749  	if curCtx.P != NoProc {
   750  		pState, ok := o.pStates[curCtx.P]
   751  		if !ok {
   752  			return curCtx, false, fmt.Errorf("found invalid proc %d during %s", curCtx.P, go122.EventString(ev.typ))
   753  		}
   754  		if pState.status != go122.ProcSyscall {
   755  			return curCtx, false, fmt.Errorf("proc %d in unexpected state %s during %s", curCtx.P, pState.status, go122.EventString(ev.typ))
   756  		}
   757  		// See the go122-create-syscall-reuse-thread-id test case for more details.
   758  		pState.status = go122.ProcSyscallAbandoned
   759  		newCtx.P = NoProc
   760  
   761  		// Queue an extra self-ProcSteal event.
   762  		extra := makeEvent(evt, curCtx, go122.EvProcSteal, ev.time, uint64(curCtx.P))
   763  		extra.base.extra(version.Go122)[0] = uint64(go122.ProcSyscall)
   764  		o.queue.push(extra)
   765  	}
   766  	o.queue.push(Event{table: evt, ctx: curCtx, base: *ev})
   767  	return newCtx, true, nil
   768  }
   769  
   770  func (o *ordering) advanceUserTaskBegin(ev *baseEvent, evt *evTable, m ThreadID, gen uint64, curCtx schedCtx) (schedCtx, bool, error) {
   771  	// Handle tasks. Tasks are interesting because:
   772  	// - There's no Begin event required to reference a task.
   773  	// - End for a particular task ID can appear multiple times.
   774  	// As a result, there's very little to validate. The only
   775  	// thing we have to be sure of is that a task didn't begin
   776  	// after it had already begun. Task IDs are allowed to be
   777  	// reused, so we don't care about a Begin after an End.
   778  	id := TaskID(ev.args[0])
   779  	if _, ok := o.activeTasks[id]; ok {
   780  		return curCtx, false, fmt.Errorf("task ID conflict: %d", id)
   781  	}
   782  	// Get the parent ID, but don't validate it. There's no guarantee
   783  	// we actually have information on whether it's active.
   784  	parentID := TaskID(ev.args[1])
   785  	if parentID == BackgroundTask {
   786  		// Note: a value of 0 here actually means no parent, *not* the
   787  		// background task. Automatic background task attachment only
   788  		// applies to regions.
   789  		parentID = NoTask
   790  		ev.args[1] = uint64(NoTask)
   791  	}
   792  
   793  	// Validate the name and record it. We'll need to pass it through to
   794  	// EvUserTaskEnd.
   795  	nameID := stringID(ev.args[2])
   796  	name, ok := evt.strings.get(nameID)
   797  	if !ok {
   798  		return curCtx, false, fmt.Errorf("invalid string ID %v for %v event", nameID, ev.typ)
   799  	}
   800  	o.activeTasks[id] = taskState{name: name, parentID: parentID}
   801  	if err := validateCtx(curCtx, event.UserGoReqs); err != nil {
   802  		return curCtx, false, err
   803  	}
   804  	o.queue.push(Event{table: evt, ctx: curCtx, base: *ev})
   805  	return curCtx, true, nil
   806  }
   807  
   808  func (o *ordering) advanceUserTaskEnd(ev *baseEvent, evt *evTable, m ThreadID, gen uint64, curCtx schedCtx) (schedCtx, bool, error) {
   809  	id := TaskID(ev.args[0])
   810  	if ts, ok := o.activeTasks[id]; ok {
   811  		// Smuggle the task info. This may happen in a different generation,
   812  		// which may not have the name in its string table. Add it to the extra
   813  		// strings table so we can look it up later.
   814  		ev.extra(version.Go122)[0] = uint64(ts.parentID)
   815  		ev.extra(version.Go122)[1] = uint64(evt.addExtraString(ts.name))
   816  		delete(o.activeTasks, id)
   817  	} else {
   818  		// Explicitly clear the task info.
   819  		ev.extra(version.Go122)[0] = uint64(NoTask)
   820  		ev.extra(version.Go122)[1] = uint64(evt.addExtraString(""))
   821  	}
   822  	if err := validateCtx(curCtx, event.UserGoReqs); err != nil {
   823  		return curCtx, false, err
   824  	}
   825  	o.queue.push(Event{table: evt, ctx: curCtx, base: *ev})
   826  	return curCtx, true, nil
   827  }
   828  
   829  func (o *ordering) advanceUserRegionBegin(ev *baseEvent, evt *evTable, m ThreadID, gen uint64, curCtx schedCtx) (schedCtx, bool, error) {
   830  	if err := validateCtx(curCtx, event.UserGoReqs); err != nil {
   831  		return curCtx, false, err
   832  	}
   833  	tid := TaskID(ev.args[0])
   834  	nameID := stringID(ev.args[1])
   835  	name, ok := evt.strings.get(nameID)
   836  	if !ok {
   837  		return curCtx, false, fmt.Errorf("invalid string ID %v for %v event", nameID, ev.typ)
   838  	}
   839  	gState, ok := o.gStates[curCtx.G]
   840  	if !ok {
   841  		return curCtx, false, fmt.Errorf("encountered EvUserRegionBegin without known state for current goroutine %d", curCtx.G)
   842  	}
   843  	if err := gState.beginRegion(userRegion{tid, name}); err != nil {
   844  		return curCtx, false, err
   845  	}
   846  	o.queue.push(Event{table: evt, ctx: curCtx, base: *ev})
   847  	return curCtx, true, nil
   848  }
   849  
   850  func (o *ordering) advanceUserRegionEnd(ev *baseEvent, evt *evTable, m ThreadID, gen uint64, curCtx schedCtx) (schedCtx, bool, error) {
   851  	if err := validateCtx(curCtx, event.UserGoReqs); err != nil {
   852  		return curCtx, false, err
   853  	}
   854  	tid := TaskID(ev.args[0])
   855  	nameID := stringID(ev.args[1])
   856  	name, ok := evt.strings.get(nameID)
   857  	if !ok {
   858  		return curCtx, false, fmt.Errorf("invalid string ID %v for %v event", nameID, ev.typ)
   859  	}
   860  	gState, ok := o.gStates[curCtx.G]
   861  	if !ok {
   862  		return curCtx, false, fmt.Errorf("encountered EvUserRegionEnd without known state for current goroutine %d", curCtx.G)
   863  	}
   864  	if err := gState.endRegion(userRegion{tid, name}); err != nil {
   865  		return curCtx, false, err
   866  	}
   867  	o.queue.push(Event{table: evt, ctx: curCtx, base: *ev})
   868  	return curCtx, true, nil
   869  }
   870  
   871  // Handle the GC mark phase.
   872  //
   873  // We have sequence numbers for both start and end because they
   874  // can happen on completely different threads. We want an explicit
   875  // partial order edge between start and end here, otherwise we're
   876  // relying entirely on timestamps to make sure we don't advance a
   877  // GCEnd for a _different_ GC cycle if timestamps are wildly broken.
   878  func (o *ordering) advanceGCActive(ev *baseEvent, evt *evTable, m ThreadID, gen uint64, curCtx schedCtx) (schedCtx, bool, error) {
   879  	seq := ev.args[0]
   880  	if gen == o.initialGen {
   881  		if o.gcState != gcUndetermined {
   882  			return curCtx, false, fmt.Errorf("GCActive in the first generation isn't first GC event")
   883  		}
   884  		o.gcSeq = seq
   885  		o.gcState = gcRunning
   886  		o.queue.push(Event{table: evt, ctx: curCtx, base: *ev})
   887  		return curCtx, true, nil
   888  	}
   889  	if seq != o.gcSeq+1 {
   890  		// This is not the right GC cycle.
   891  		return curCtx, false, nil
   892  	}
   893  	if o.gcState != gcRunning {
   894  		return curCtx, false, fmt.Errorf("encountered GCActive while GC was not in progress")
   895  	}
   896  	o.gcSeq = seq
   897  	if err := validateCtx(curCtx, event.UserGoReqs); err != nil {
   898  		return curCtx, false, err
   899  	}
   900  	o.queue.push(Event{table: evt, ctx: curCtx, base: *ev})
   901  	return curCtx, true, nil
   902  }
   903  
   904  func (o *ordering) advanceGCBegin(ev *baseEvent, evt *evTable, m ThreadID, gen uint64, curCtx schedCtx) (schedCtx, bool, error) {
   905  	seq := ev.args[0]
   906  	if o.gcState == gcUndetermined {
   907  		o.gcSeq = seq
   908  		o.gcState = gcRunning
   909  		o.queue.push(Event{table: evt, ctx: curCtx, base: *ev})
   910  		return curCtx, true, nil
   911  	}
   912  	if seq != o.gcSeq+1 {
   913  		// This is not the right GC cycle.
   914  		return curCtx, false, nil
   915  	}
   916  	if o.gcState == gcRunning {
   917  		return curCtx, false, fmt.Errorf("encountered GCBegin while GC was already in progress")
   918  	}
   919  	o.gcSeq = seq
   920  	o.gcState = gcRunning
   921  	if err := validateCtx(curCtx, event.UserGoReqs); err != nil {
   922  		return curCtx, false, err
   923  	}
   924  	o.queue.push(Event{table: evt, ctx: curCtx, base: *ev})
   925  	return curCtx, true, nil
   926  }
   927  
   928  func (o *ordering) advanceGCEnd(ev *baseEvent, evt *evTable, m ThreadID, gen uint64, curCtx schedCtx) (schedCtx, bool, error) {
   929  	seq := ev.args[0]
   930  	if seq != o.gcSeq+1 {
   931  		// This is not the right GC cycle.
   932  		return curCtx, false, nil
   933  	}
   934  	if o.gcState == gcNotRunning {
   935  		return curCtx, false, fmt.Errorf("encountered GCEnd when GC was not in progress")
   936  	}
   937  	if o.gcState == gcUndetermined {
   938  		return curCtx, false, fmt.Errorf("encountered GCEnd when GC was in an undetermined state")
   939  	}
   940  	o.gcSeq = seq
   941  	o.gcState = gcNotRunning
   942  	if err := validateCtx(curCtx, event.UserGoReqs); err != nil {
   943  		return curCtx, false, err
   944  	}
   945  	o.queue.push(Event{table: evt, ctx: curCtx, base: *ev})
   946  	return curCtx, true, nil
   947  }
   948  
   949  func (o *ordering) advanceAnnotation(ev *baseEvent, evt *evTable, m ThreadID, gen uint64, curCtx schedCtx) (schedCtx, bool, error) {
   950  	// Handle simple instantaneous events that require a G.
   951  	if err := validateCtx(curCtx, event.UserGoReqs); err != nil {
   952  		return curCtx, false, err
   953  	}
   954  	o.queue.push(Event{table: evt, ctx: curCtx, base: *ev})
   955  	return curCtx, true, nil
   956  }
   957  
   958  func (o *ordering) advanceHeapMetric(ev *baseEvent, evt *evTable, m ThreadID, gen uint64, curCtx schedCtx) (schedCtx, bool, error) {
   959  	// Handle allocation metrics, which don't require a G.
   960  	if err := validateCtx(curCtx, event.SchedReqs{Thread: event.MustHave, Proc: event.MustHave, Goroutine: event.MayHave}); err != nil {
   961  		return curCtx, false, err
   962  	}
   963  	o.queue.push(Event{table: evt, ctx: curCtx, base: *ev})
   964  	return curCtx, true, nil
   965  }
   966  
   967  func (o *ordering) advanceGCSweepBegin(ev *baseEvent, evt *evTable, m ThreadID, gen uint64, curCtx schedCtx) (schedCtx, bool, error) {
   968  	// Handle sweep, which is bound to a P and doesn't require a G.
   969  	if err := validateCtx(curCtx, event.SchedReqs{Thread: event.MustHave, Proc: event.MustHave, Goroutine: event.MayHave}); err != nil {
   970  		return curCtx, false, err
   971  	}
   972  	if err := o.pStates[curCtx.P].beginRange(makeRangeType(ev.typ, 0)); err != nil {
   973  		return curCtx, false, err
   974  	}
   975  	o.queue.push(Event{table: evt, ctx: curCtx, base: *ev})
   976  	return curCtx, true, nil
   977  }
   978  
   979  func (o *ordering) advanceGCSweepActive(ev *baseEvent, evt *evTable, m ThreadID, gen uint64, curCtx schedCtx) (schedCtx, bool, error) {
   980  	pid := ProcID(ev.args[0])
   981  	// N.B. In practice Ps can't block while they're sweeping, so this can only
   982  	// ever reference curCtx.P. However, be lenient about this like we are with
   983  	// GCMarkAssistActive; there's no reason the runtime couldn't change to block
   984  	// in the middle of a sweep.
   985  	pState, ok := o.pStates[pid]
   986  	if !ok {
   987  		return curCtx, false, fmt.Errorf("encountered GCSweepActive for unknown proc %d", pid)
   988  	}
   989  	if err := pState.activeRange(makeRangeType(ev.typ, 0), gen == o.initialGen); err != nil {
   990  		return curCtx, false, err
   991  	}
   992  	o.queue.push(Event{table: evt, ctx: curCtx, base: *ev})
   993  	return curCtx, true, nil
   994  }
   995  
   996  func (o *ordering) advanceGCSweepEnd(ev *baseEvent, evt *evTable, m ThreadID, gen uint64, curCtx schedCtx) (schedCtx, bool, error) {
   997  	if err := validateCtx(curCtx, event.SchedReqs{Thread: event.MustHave, Proc: event.MustHave, Goroutine: event.MayHave}); err != nil {
   998  		return curCtx, false, err
   999  	}
  1000  	_, err := o.pStates[curCtx.P].endRange(ev.typ)
  1001  	if err != nil {
  1002  		return curCtx, false, err
  1003  	}
  1004  	o.queue.push(Event{table: evt, ctx: curCtx, base: *ev})
  1005  	return curCtx, true, nil
  1006  }
  1007  
  1008  func (o *ordering) advanceGoRangeBegin(ev *baseEvent, evt *evTable, m ThreadID, gen uint64, curCtx schedCtx) (schedCtx, bool, error) {
  1009  	// Handle special goroutine-bound event ranges.
  1010  	if err := validateCtx(curCtx, event.UserGoReqs); err != nil {
  1011  		return curCtx, false, err
  1012  	}
  1013  	desc := stringID(0)
  1014  	if ev.typ == go122.EvSTWBegin {
  1015  		desc = stringID(ev.args[0])
  1016  	}
  1017  	gState, ok := o.gStates[curCtx.G]
  1018  	if !ok {
  1019  		return curCtx, false, fmt.Errorf("encountered event of type %d without known state for current goroutine %d", ev.typ, curCtx.G)
  1020  	}
  1021  	if err := gState.beginRange(makeRangeType(ev.typ, desc)); err != nil {
  1022  		return curCtx, false, err
  1023  	}
  1024  	o.queue.push(Event{table: evt, ctx: curCtx, base: *ev})
  1025  	return curCtx, true, nil
  1026  }
  1027  
  1028  func (o *ordering) advanceGoRangeActive(ev *baseEvent, evt *evTable, m ThreadID, gen uint64, curCtx schedCtx) (schedCtx, bool, error) {
  1029  	gid := GoID(ev.args[0])
  1030  	// N.B. Like GoStatus, this can happen at any time, because it can
  1031  	// reference a non-running goroutine. Don't check anything about the
  1032  	// current scheduler context.
  1033  	gState, ok := o.gStates[gid]
  1034  	if !ok {
  1035  		return curCtx, false, fmt.Errorf("uninitialized goroutine %d found during %s", gid, go122.EventString(ev.typ))
  1036  	}
  1037  	if err := gState.activeRange(makeRangeType(ev.typ, 0), gen == o.initialGen); err != nil {
  1038  		return curCtx, false, err
  1039  	}
  1040  	o.queue.push(Event{table: evt, ctx: curCtx, base: *ev})
  1041  	return curCtx, true, nil
  1042  }
  1043  
  1044  func (o *ordering) advanceGoRangeEnd(ev *baseEvent, evt *evTable, m ThreadID, gen uint64, curCtx schedCtx) (schedCtx, bool, error) {
  1045  	if err := validateCtx(curCtx, event.UserGoReqs); err != nil {
  1046  		return curCtx, false, err
  1047  	}
  1048  	gState, ok := o.gStates[curCtx.G]
  1049  	if !ok {
  1050  		return curCtx, false, fmt.Errorf("encountered event of type %d without known state for current goroutine %d", ev.typ, curCtx.G)
  1051  	}
  1052  	desc, err := gState.endRange(ev.typ)
  1053  	if err != nil {
  1054  		return curCtx, false, err
  1055  	}
  1056  	if ev.typ == go122.EvSTWEnd {
  1057  		// Smuggle the kind into the event.
  1058  		// Don't use ev.extra here so we have symmetry with STWBegin.
  1059  		ev.args[0] = uint64(desc)
  1060  	}
  1061  	o.queue.push(Event{table: evt, ctx: curCtx, base: *ev})
  1062  	return curCtx, true, nil
  1063  }
  1064  
  1065  // Next returns the next event in the ordering.
  1066  func (o *ordering) Next() (Event, bool) {
  1067  	return o.queue.pop()
  1068  }
  1069  
  1070  // schedCtx represents the scheduling resources associated with an event.
  1071  type schedCtx struct {
  1072  	G GoID
  1073  	P ProcID
  1074  	M ThreadID
  1075  }
  1076  
  1077  // validateCtx ensures that ctx conforms to some reqs, returning an error if
  1078  // it doesn't.
  1079  func validateCtx(ctx schedCtx, reqs event.SchedReqs) error {
  1080  	// Check thread requirements.
  1081  	if reqs.Thread == event.MustHave && ctx.M == NoThread {
  1082  		return fmt.Errorf("expected a thread but didn't have one")
  1083  	} else if reqs.Thread == event.MustNotHave && ctx.M != NoThread {
  1084  		return fmt.Errorf("expected no thread but had one")
  1085  	}
  1086  
  1087  	// Check proc requirements.
  1088  	if reqs.Proc == event.MustHave && ctx.P == NoProc {
  1089  		return fmt.Errorf("expected a proc but didn't have one")
  1090  	} else if reqs.Proc == event.MustNotHave && ctx.P != NoProc {
  1091  		return fmt.Errorf("expected no proc but had one")
  1092  	}
  1093  
  1094  	// Check goroutine requirements.
  1095  	if reqs.Goroutine == event.MustHave && ctx.G == NoGoroutine {
  1096  		return fmt.Errorf("expected a goroutine but didn't have one")
  1097  	} else if reqs.Goroutine == event.MustNotHave && ctx.G != NoGoroutine {
  1098  		return fmt.Errorf("expected no goroutine but had one")
  1099  	}
  1100  	return nil
  1101  }
  1102  
  1103  // gcState is a trinary variable for the current state of the GC.
  1104  //
  1105  // The third state besides "enabled" and "disabled" is "undetermined."
  1106  type gcState uint8
  1107  
  1108  const (
  1109  	gcUndetermined gcState = iota
  1110  	gcNotRunning
  1111  	gcRunning
  1112  )
  1113  
  1114  // String returns a human-readable string for the GC state.
  1115  func (s gcState) String() string {
  1116  	switch s {
  1117  	case gcUndetermined:
  1118  		return "Undetermined"
  1119  	case gcNotRunning:
  1120  		return "NotRunning"
  1121  	case gcRunning:
  1122  		return "Running"
  1123  	}
  1124  	return "Bad"
  1125  }
  1126  
  1127  // userRegion represents a unique user region when attached to some gState.
  1128  type userRegion struct {
  1129  	// name must be a resolved string because the string ID for the same
  1130  	// string may change across generations, but we care about checking
  1131  	// the value itself.
  1132  	taskID TaskID
  1133  	name   string
  1134  }
  1135  
  1136  // rangeType is a way to classify special ranges of time.
  1137  //
  1138  // These typically correspond 1:1 with "Begin" events, but
  1139  // they may have an optional subtype that describes the range
  1140  // in more detail.
  1141  type rangeType struct {
  1142  	typ  event.Type // "Begin" event.
  1143  	desc stringID   // Optional subtype.
  1144  }
  1145  
  1146  // makeRangeType constructs a new rangeType.
  1147  func makeRangeType(typ event.Type, desc stringID) rangeType {
  1148  	if styp := go122.Specs()[typ].StartEv; styp != go122.EvNone {
  1149  		typ = styp
  1150  	}
  1151  	return rangeType{typ, desc}
  1152  }
  1153  
  1154  // gState is the state of a goroutine at a point in the trace.
  1155  type gState struct {
  1156  	id     GoID
  1157  	status go122.GoStatus
  1158  	seq    seqCounter
  1159  
  1160  	// regions are the active user regions for this goroutine.
  1161  	regions []userRegion
  1162  
  1163  	// rangeState is the state of special time ranges bound to this goroutine.
  1164  	rangeState
  1165  }
  1166  
  1167  // beginRegion starts a user region on the goroutine.
  1168  func (s *gState) beginRegion(r userRegion) error {
  1169  	s.regions = append(s.regions, r)
  1170  	return nil
  1171  }
  1172  
  1173  // endRegion ends a user region on the goroutine.
  1174  func (s *gState) endRegion(r userRegion) error {
  1175  	if len(s.regions) == 0 {
  1176  		// We do not know about regions that began before tracing started.
  1177  		return nil
  1178  	}
  1179  	if next := s.regions[len(s.regions)-1]; next != r {
  1180  		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)
  1181  	}
  1182  	s.regions = s.regions[:len(s.regions)-1]
  1183  	return nil
  1184  }
  1185  
  1186  // pState is the state of a proc at a point in the trace.
  1187  type pState struct {
  1188  	id     ProcID
  1189  	status go122.ProcStatus
  1190  	seq    seqCounter
  1191  
  1192  	// rangeState is the state of special time ranges bound to this proc.
  1193  	rangeState
  1194  }
  1195  
  1196  // mState is the state of a thread at a point in the trace.
  1197  type mState struct {
  1198  	g GoID   // Goroutine bound to this M. (The goroutine's state is Executing.)
  1199  	p ProcID // Proc bound to this M. (The proc's state is Executing.)
  1200  }
  1201  
  1202  // rangeState represents the state of special time ranges.
  1203  type rangeState struct {
  1204  	// inFlight contains the rangeTypes of any ranges bound to a resource.
  1205  	inFlight []rangeType
  1206  }
  1207  
  1208  // beginRange begins a special range in time on the goroutine.
  1209  //
  1210  // Returns an error if the range is already in progress.
  1211  func (s *rangeState) beginRange(typ rangeType) error {
  1212  	if s.hasRange(typ) {
  1213  		return fmt.Errorf("discovered event already in-flight for when starting event %v", go122.Specs()[typ.typ].Name)
  1214  	}
  1215  	s.inFlight = append(s.inFlight, typ)
  1216  	return nil
  1217  }
  1218  
  1219  // activeRange marks special range in time on the goroutine as active in the
  1220  // initial generation, or confirms that it is indeed active in later generations.
  1221  func (s *rangeState) activeRange(typ rangeType, isInitialGen bool) error {
  1222  	if isInitialGen {
  1223  		if s.hasRange(typ) {
  1224  			return fmt.Errorf("found named active range already in first gen: %v", typ)
  1225  		}
  1226  		s.inFlight = append(s.inFlight, typ)
  1227  	} else if !s.hasRange(typ) {
  1228  		return fmt.Errorf("resource is missing active range: %v %v", go122.Specs()[typ.typ].Name, s.inFlight)
  1229  	}
  1230  	return nil
  1231  }
  1232  
  1233  // hasRange returns true if a special time range on the goroutine as in progress.
  1234  func (s *rangeState) hasRange(typ rangeType) bool {
  1235  	for _, ftyp := range s.inFlight {
  1236  		if ftyp == typ {
  1237  			return true
  1238  		}
  1239  	}
  1240  	return false
  1241  }
  1242  
  1243  // endRange ends a special range in time on the goroutine.
  1244  //
  1245  // This must line up with the start event type  of the range the goroutine is currently in.
  1246  func (s *rangeState) endRange(typ event.Type) (stringID, error) {
  1247  	st := go122.Specs()[typ].StartEv
  1248  	idx := -1
  1249  	for i, r := range s.inFlight {
  1250  		if r.typ == st {
  1251  			idx = i
  1252  			break
  1253  		}
  1254  	}
  1255  	if idx < 0 {
  1256  		return 0, fmt.Errorf("tried to end event %v, but not in-flight", go122.Specs()[st].Name)
  1257  	}
  1258  	// Swap remove.
  1259  	desc := s.inFlight[idx].desc
  1260  	s.inFlight[idx], s.inFlight[len(s.inFlight)-1] = s.inFlight[len(s.inFlight)-1], s.inFlight[idx]
  1261  	s.inFlight = s.inFlight[:len(s.inFlight)-1]
  1262  	return desc, nil
  1263  }
  1264  
  1265  // seqCounter represents a global sequence counter for a resource.
  1266  type seqCounter struct {
  1267  	gen uint64 // The generation for the local sequence counter seq.
  1268  	seq uint64 // The sequence number local to the generation.
  1269  }
  1270  
  1271  // makeSeq creates a new seqCounter.
  1272  func makeSeq(gen, seq uint64) seqCounter {
  1273  	return seqCounter{gen: gen, seq: seq}
  1274  }
  1275  
  1276  // succeeds returns true if a is the immediate successor of b.
  1277  func (a seqCounter) succeeds(b seqCounter) bool {
  1278  	return a.gen == b.gen && a.seq == b.seq+1
  1279  }
  1280  
  1281  // String returns a debug string representation of the seqCounter.
  1282  func (c seqCounter) String() string {
  1283  	return fmt.Sprintf("%d (gen=%d)", c.seq, c.gen)
  1284  }
  1285  
  1286  func dumpOrdering(order *ordering) string {
  1287  	var sb strings.Builder
  1288  	for id, state := range order.gStates {
  1289  		fmt.Fprintf(&sb, "G %d [status=%s seq=%s]\n", id, state.status, state.seq)
  1290  	}
  1291  	fmt.Fprintln(&sb)
  1292  	for id, state := range order.pStates {
  1293  		fmt.Fprintf(&sb, "P %d [status=%s seq=%s]\n", id, state.status, state.seq)
  1294  	}
  1295  	fmt.Fprintln(&sb)
  1296  	for id, state := range order.mStates {
  1297  		fmt.Fprintf(&sb, "M %d [g=%d p=%d]\n", id, state.g, state.p)
  1298  	}
  1299  	fmt.Fprintln(&sb)
  1300  	fmt.Fprintf(&sb, "GC %d %s\n", order.gcSeq, order.gcState)
  1301  	return sb.String()
  1302  }
  1303  
  1304  // taskState represents an active task.
  1305  type taskState struct {
  1306  	// name is the type of the active task.
  1307  	name string
  1308  
  1309  	// parentID is the parent ID of the active task.
  1310  	parentID TaskID
  1311  }
  1312  
  1313  // queue implements a growable ring buffer with a queue API.
  1314  type queue[T any] struct {
  1315  	start, end int
  1316  	buf        []T
  1317  }
  1318  
  1319  // push adds a new event to the back of the queue.
  1320  func (q *queue[T]) push(value T) {
  1321  	if q.end-q.start == len(q.buf) {
  1322  		q.grow()
  1323  	}
  1324  	q.buf[q.end%len(q.buf)] = value
  1325  	q.end++
  1326  }
  1327  
  1328  // grow increases the size of the queue.
  1329  func (q *queue[T]) grow() {
  1330  	if len(q.buf) == 0 {
  1331  		q.buf = make([]T, 2)
  1332  		return
  1333  	}
  1334  
  1335  	// Create new buf and copy data over.
  1336  	newBuf := make([]T, len(q.buf)*2)
  1337  	pivot := q.start % len(q.buf)
  1338  	first, last := q.buf[pivot:], q.buf[:pivot]
  1339  	copy(newBuf[:len(first)], first)
  1340  	copy(newBuf[len(first):], last)
  1341  
  1342  	// Update the queue state.
  1343  	q.start = 0
  1344  	q.end = len(q.buf)
  1345  	q.buf = newBuf
  1346  }
  1347  
  1348  // pop removes an event from the front of the queue. If the
  1349  // queue is empty, it returns an EventBad event.
  1350  func (q *queue[T]) pop() (T, bool) {
  1351  	if q.end-q.start == 0 {
  1352  		return *new(T), false
  1353  	}
  1354  	elem := &q.buf[q.start%len(q.buf)]
  1355  	value := *elem
  1356  	*elem = *new(T) // Clear the entry before returning, so we don't hold onto old tables.
  1357  	q.start++
  1358  	return value, true
  1359  }
  1360  
  1361  // makeEvent creates an Event from the provided information.
  1362  //
  1363  // It's just a convenience function; it's always OK to construct
  1364  // an Event manually if this isn't quite the right way to express
  1365  // the contents of the event.
  1366  func makeEvent(table *evTable, ctx schedCtx, typ event.Type, time Time, args ...uint64) Event {
  1367  	ev := Event{
  1368  		table: table,
  1369  		ctx:   ctx,
  1370  		base: baseEvent{
  1371  			typ:  typ,
  1372  			time: time,
  1373  		},
  1374  	}
  1375  	copy(ev.base.args[:], args)
  1376  	return ev
  1377  }
  1378  

View as plain text