1// Copyright 2024 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
5package oldtrace
6
7import "errors"
8
9type orderEvent struct {
10	ev   Event
11	proc *proc
12}
13
14type gStatus int
15
16type gState struct {
17	seq    uint64
18	status gStatus
19}
20
21const (
22	gDead gStatus = iota
23	gRunnable
24	gRunning
25	gWaiting
26
27	unordered = ^uint64(0)
28	garbage   = ^uint64(0) - 1
29	noseq     = ^uint64(0)
30	seqinc    = ^uint64(0) - 1
31)
32
33// stateTransition returns goroutine state (sequence and status) when the event
34// becomes ready for merging (init) and the goroutine state after the event (next).
35func stateTransition(ev *Event) (g uint64, init, next gState) {
36	// Note that we have an explicit return in each case, as that produces slightly better code (tested on Go 1.19).
37
38	switch ev.Type {
39	case EvGoCreate:
40		g = ev.Args[0]
41		init = gState{0, gDead}
42		next = gState{1, gRunnable}
43		return
44	case EvGoWaiting, EvGoInSyscall:
45		g = ev.G
46		init = gState{1, gRunnable}
47		next = gState{2, gWaiting}
48		return
49	case EvGoStart, EvGoStartLabel:
50		g = ev.G
51		init = gState{ev.Args[1], gRunnable}
52		next = gState{ev.Args[1] + 1, gRunning}
53		return
54	case EvGoStartLocal:
55		// noseq means that this event is ready for merging as soon as
56		// frontier reaches it (EvGoStartLocal is emitted on the same P
57		// as the corresponding EvGoCreate/EvGoUnblock, and thus the latter
58		// is already merged).
59		// seqinc is a stub for cases when event increments g sequence,
60		// but since we don't know current seq we also don't know next seq.
61		g = ev.G
62		init = gState{noseq, gRunnable}
63		next = gState{seqinc, gRunning}
64		return
65	case EvGoBlock, EvGoBlockSend, EvGoBlockRecv, EvGoBlockSelect,
66		EvGoBlockSync, EvGoBlockCond, EvGoBlockNet, EvGoSleep,
67		EvGoSysBlock, EvGoBlockGC:
68		g = ev.G
69		init = gState{noseq, gRunning}
70		next = gState{noseq, gWaiting}
71		return
72	case EvGoSched, EvGoPreempt:
73		g = ev.G
74		init = gState{noseq, gRunning}
75		next = gState{noseq, gRunnable}
76		return
77	case EvGoUnblock, EvGoSysExit:
78		g = ev.Args[0]
79		init = gState{ev.Args[1], gWaiting}
80		next = gState{ev.Args[1] + 1, gRunnable}
81		return
82	case EvGoUnblockLocal, EvGoSysExitLocal:
83		g = ev.Args[0]
84		init = gState{noseq, gWaiting}
85		next = gState{seqinc, gRunnable}
86		return
87	case EvGCStart:
88		g = garbage
89		init = gState{ev.Args[0], gDead}
90		next = gState{ev.Args[0] + 1, gDead}
91		return
92	default:
93		// no ordering requirements
94		g = unordered
95		return
96	}
97}
98
99func transitionReady(g uint64, curr, init gState) bool {
100	return g == unordered || (init.seq == noseq || init.seq == curr.seq) && init.status == curr.status
101}
102
103func transition(gs map[uint64]gState, g uint64, init, next gState) error {
104	if g == unordered {
105		return nil
106	}
107	curr := gs[g]
108	if !transitionReady(g, curr, init) {
109		// See comment near the call to transition, where we're building the frontier, for details on how this could
110		// possibly happen.
111		return errors.New("encountered impossible goroutine state transition")
112	}
113	switch next.seq {
114	case noseq:
115		next.seq = curr.seq
116	case seqinc:
117		next.seq = curr.seq + 1
118	}
119	gs[g] = next
120	return nil
121}
122
123type orderEventList []orderEvent
124
125func (l *orderEventList) Less(i, j int) bool {
126	return (*l)[i].ev.Ts < (*l)[j].ev.Ts
127}
128
129func (h *orderEventList) Push(x orderEvent) {
130	*h = append(*h, x)
131	heapUp(h, len(*h)-1)
132}
133
134func (h *orderEventList) Pop() orderEvent {
135	n := len(*h) - 1
136	(*h)[0], (*h)[n] = (*h)[n], (*h)[0]
137	heapDown(h, 0, n)
138	x := (*h)[len(*h)-1]
139	*h = (*h)[:len(*h)-1]
140	return x
141}
142
143func heapUp(h *orderEventList, j int) {
144	for {
145		i := (j - 1) / 2 // parent
146		if i == j || !h.Less(j, i) {
147			break
148		}
149		(*h)[i], (*h)[j] = (*h)[j], (*h)[i]
150		j = i
151	}
152}
153
154func heapDown(h *orderEventList, i0, n int) bool {
155	i := i0
156	for {
157		j1 := 2*i + 1
158		if j1 >= n || j1 < 0 { // j1 < 0 after int overflow
159			break
160		}
161		j := j1 // left child
162		if j2 := j1 + 1; j2 < n && h.Less(j2, j1) {
163			j = j2 // = 2*i + 2  // right child
164		}
165		if !h.Less(j, i) {
166			break
167		}
168		(*h)[i], (*h)[j] = (*h)[j], (*h)[i]
169		i = j
170	}
171	return i > i0
172}
173