// Copyright 2016 The Go Authors. All rights reserved.
|
// Use of this source code is governed by a BSD-style
|
// license that can be found in the LICENSE file.
|
|
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
|
)
|
|
// order1007 merges a set of per-P event batches into a single, consistent stream.
|
// The high level idea is as follows. Events within an individual batch are in
|
// correct order, because they are emitted by a single P. So we need to produce
|
// a correct interleaving of the batches. To do this we take first unmerged event
|
// from each batch (frontier). Then choose subset that is "ready" to be merged,
|
// that is, events for which all dependencies are already merged. Then we choose
|
// event with the lowest timestamp from the subset, merge it and repeat.
|
// This approach ensures that we form a consistent stream even if timestamps are
|
// incorrect (condition observed on some machines).
|
func order1007(m map[int][]*Event) (events []*Event, err error) {
|
pending := 0
|
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
|
// Get rid of "Local" events, they are intended merely for ordering.
|
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
|
}
|
|
// At this point we have a consistent stream of events.
|
// Make sure time stamps respect the ordering.
|
// The tests will skip (not fail) the test case if they see this error.
|
if !sort.IsSorted(eventList(events)) {
|
return nil, ErrTimeOrder
|
}
|
|
// The last part is giving correct timestamps to EvGoSysExit events.
|
// The problem with EvGoSysExit is that actual syscall exit timestamp (ev.Args[2])
|
// is potentially acquired long before event emission. So far we've used
|
// timestamp of event emission (ev.Ts).
|
// We could not set ev.Ts = ev.Args[2] earlier, because it would produce
|
// seemingly broken timestamps (misplaced event).
|
// We also can't simply update the timestamp and resort events, because
|
// if timestamps are broken we will misplace the event and later report
|
// logically broken trace (instead of reporting broken timestamps).
|
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
|
}
|
|
// stateTransition returns goroutine state (sequence and status) when the event
|
// becomes ready for merging (init) and the goroutine state after the event (next).
|
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:
|
// noseq means that this event is ready for merging as soon as
|
// frontier reaches it (EvGoStartLocal is emitted on the same P
|
// as the corresponding EvGoCreate/EvGoUnblock, and thus the latter
|
// is already merged).
|
// seqinc is a stub for cases when event increments g sequence,
|
// but since we don't know current seq we also don't know next seq.
|
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:
|
// no ordering requirements
|
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
|
}
|
|
// order1005 merges a set of per-P event batches into a single, consistent stream.
|
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 {
|
// EvGoSysExit emission is delayed until the thread has a P.
|
// Give it the real sequence number and time stamp.
|
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]
|
}
|
