order.go

Documentation: golang.org/x/exp/trace/internal/oldtrace

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