package trace
import (
"fmt"
"sort"
)
type eventBatch struct {
events []*Event
selected bool
}
type orderEvent struct {
ev *Event
batch int
g uint64
init gState
next gState
}
type gStatus int
type gState struct {
seq uint64
status gStatus
}
const (
gDead gStatus = iota
gRunnable
gRunning
gWaiting
unordered = ^uint64 (0 )
garbage = ^uint64 (0 ) - 1
noseq = ^uint64 (0 )
seqinc = ^uint64 (0 ) - 1
)
func order1007(m map [int ][]*Event ) (events []*Event , err error ) {
pending := 0
sort .Stable (eventList (m [ProfileP ]))
var batches []*eventBatch
for _ , v := range m {
pending += len (v )
batches = append (batches , &eventBatch {v , false })
}
gs := make (map [uint64 ]gState )
var frontier []orderEvent
for ; pending != 0 ; pending -- {
for i , b := range batches {
if b .selected || len (b .events ) == 0 {
continue
}
ev := b .events [0 ]
g , init , next := stateTransition (ev )
if !transitionReady (g , gs [g ], init ) {
continue
}
frontier = append (frontier , orderEvent {ev , i , g , init , next })
b .events = b .events [1 :]
b .selected = true
switch ev .Type {
case EvGoStartLocal :
ev .Type = EvGoStart
case EvGoUnblockLocal :
ev .Type = EvGoUnblock
case EvGoSysExitLocal :
ev .Type = EvGoSysExit
}
}
if len (frontier ) == 0 {
return nil , fmt .Errorf ("no consistent ordering of events possible" )
}
sort .Sort (orderEventList (frontier ))
f := frontier [0 ]
frontier [0 ] = frontier [len (frontier )-1 ]
frontier = frontier [:len (frontier )-1 ]
events = append (events , f .ev )
transition (gs , f .g , f .init , f .next )
if !batches [f .batch ].selected {
panic ("frontier batch is not selected" )
}
batches [f .batch ].selected = false
}
if !sort .IsSorted (eventList (events )) {
return nil , ErrTimeOrder
}
lastSysBlock := make (map [uint64 ]int64 )
for _ , ev := range events {
switch ev .Type {
case EvGoSysBlock , EvGoInSyscall :
lastSysBlock [ev .G ] = ev .Ts
case EvGoSysExit :
ts := int64 (ev .Args [2 ])
if ts == 0 {
continue
}
block := lastSysBlock [ev .G ]
if block == 0 {
return nil , fmt .Errorf ("stray syscall exit" )
}
if ts < block {
return nil , ErrTimeOrder
}
ev .Ts = ts
}
}
sort .Stable (eventList (events ))
return
}
func stateTransition(ev *Event ) (g uint64 , init , next gState ) {
switch ev .Type {
case EvGoCreate :
g = ev .Args [0 ]
init = gState {0 , gDead }
next = gState {1 , gRunnable }
case EvGoWaiting , EvGoInSyscall :
g = ev .G
init = gState {1 , gRunnable }
next = gState {2 , gWaiting }
case EvGoStart , EvGoStartLabel :
g = ev .G
init = gState {ev .Args [1 ], gRunnable }
next = gState {ev .Args [1 ] + 1 , gRunning }
case EvGoStartLocal :
g = ev .G
init = gState {noseq , gRunnable }
next = gState {seqinc , gRunning }
case EvGoBlock , EvGoBlockSend , EvGoBlockRecv , EvGoBlockSelect ,
EvGoBlockSync , EvGoBlockCond , EvGoBlockNet , EvGoSleep ,
EvGoSysBlock , EvGoBlockGC :
g = ev .G
init = gState {noseq , gRunning }
next = gState {noseq , gWaiting }
case EvGoSched , EvGoPreempt :
g = ev .G
init = gState {noseq , gRunning }
next = gState {noseq , gRunnable }
case EvGoUnblock , EvGoSysExit :
g = ev .Args [0 ]
init = gState {ev .Args [1 ], gWaiting }
next = gState {ev .Args [1 ] + 1 , gRunnable }
case EvGoUnblockLocal , EvGoSysExitLocal :
g = ev .Args [0 ]
init = gState {noseq , gWaiting }
next = gState {seqinc , gRunnable }
case EvGCStart :
g = garbage
init = gState {ev .Args [0 ], gDead }
next = gState {ev .Args [0 ] + 1 , gDead }
default :
g = unordered
}
return
}
func transitionReady(g uint64 , curr , init gState ) bool {
return g == unordered || (init .seq == noseq || init .seq == curr .seq ) && init .status == curr .status
}
func transition(gs map [uint64 ]gState , g uint64 , init , next gState ) {
if g == unordered {
return
}
curr := gs [g ]
if !transitionReady (g , curr , init ) {
panic ("event sequences are broken" )
}
switch next .seq {
case noseq :
next .seq = curr .seq
case seqinc :
next .seq = curr .seq + 1
}
gs [g ] = next
}
func order1005(m map [int ][]*Event ) (events []*Event , err error ) {
for _ , batch := range m {
events = append (events , batch ...)
}
for _ , ev := range events {
if ev .Type == EvGoSysExit {
ev .seq = int64 (ev .Args [1 ])
if ev .Args [2 ] != 0 {
ev .Ts = int64 (ev .Args [2 ])
}
}
}
sort .Sort (eventSeqList (events ))
if !sort .IsSorted (eventList (events )) {
return nil , ErrTimeOrder
}
return
}
type orderEventList []orderEvent
func (l orderEventList ) Len () int {
return len (l )
}
func (l orderEventList ) Less (i , j int ) bool {
return l [i ].ev .Ts < l [j ].ev .Ts
}
func (l orderEventList ) Swap (i , j int ) {
l [i ], l [j ] = l [j ], l [i ]
}
type eventList []*Event
func (l eventList ) Len () int {
return len (l )
}
func (l eventList ) Less (i , j int ) bool {
return l [i ].Ts < l [j ].Ts
}
func (l eventList ) Swap (i , j int ) {
l [i ], l [j ] = l [j ], l [i ]
}
type eventSeqList []*Event
func (l eventSeqList ) Len () int {
return len (l )
}
func (l eventSeqList ) Less (i , j int ) bool {
return l [i ].seq < l [j ].seq
}
func (l eventSeqList ) Swap (i , j int ) {
l [i ], l [j ] = l [j ], l [i ]
}
The pages are generated with Golds v0.6.9-preview . (GOOS=linux GOARCH=amd64)
Golds is a Go 101 project developed by Tapir Liu .
PR and bug reports are welcome and can be submitted to the issue list .
Please follow @Go100and1 (reachable from the left QR code) to get the latest news of Golds .