...
Run Format

Source file src/internal/trace/order.go

Documentation: internal/trace

  // 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]
  }
  

View as plain text