Source file src/pkg/internal/trace/order.go

     1	// Copyright 2016 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	package trace
     6	
     7	import (
     8		"fmt"
     9		"sort"
    10	)
    11	
    12	type eventBatch struct {
    13		events   []*Event
    14		selected bool
    15	}
    16	
    17	type orderEvent struct {
    18		ev    *Event
    19		batch int
    20		g     uint64
    21		init  gState
    22		next  gState
    23	}
    24	
    25	type gStatus int
    26	
    27	type gState struct {
    28		seq    uint64
    29		status gStatus
    30	}
    31	
    32	const (
    33		gDead gStatus = iota
    34		gRunnable
    35		gRunning
    36		gWaiting
    37	
    38		unordered = ^uint64(0)
    39		garbage   = ^uint64(0) - 1
    40		noseq     = ^uint64(0)
    41		seqinc    = ^uint64(0) - 1
    42	)
    43	
    44	// order1007 merges a set of per-P event batches into a single, consistent stream.
    45	// The high level idea is as follows. Events within an individual batch are in
    46	// correct order, because they are emitted by a single P. So we need to produce
    47	// a correct interleaving of the batches. To do this we take first unmerged event
    48	// from each batch (frontier). Then choose subset that is "ready" to be merged,
    49	// that is, events for which all dependencies are already merged. Then we choose
    50	// event with the lowest timestamp from the subset, merge it and repeat.
    51	// This approach ensures that we form a consistent stream even if timestamps are
    52	// incorrect (condition observed on some machines).
    53	func order1007(m map[int][]*Event) (events []*Event, err error) {
    54		pending := 0
    55		var batches []*eventBatch
    56		for _, v := range m {
    57			pending += len(v)
    58			batches = append(batches, &eventBatch{v, false})
    59		}
    60		gs := make(map[uint64]gState)
    61		var frontier []orderEvent
    62		for ; pending != 0; pending-- {
    63			for i, b := range batches {
    64				if b.selected || len(b.events) == 0 {
    65					continue
    66				}
    67				ev := b.events[0]
    68				g, init, next := stateTransition(ev)
    69				if !transitionReady(g, gs[g], init) {
    70					continue
    71				}
    72				frontier = append(frontier, orderEvent{ev, i, g, init, next})
    73				b.events = b.events[1:]
    74				b.selected = true
    75				// Get rid of "Local" events, they are intended merely for ordering.
    76				switch ev.Type {
    77				case EvGoStartLocal:
    78					ev.Type = EvGoStart
    79				case EvGoUnblockLocal:
    80					ev.Type = EvGoUnblock
    81				case EvGoSysExitLocal:
    82					ev.Type = EvGoSysExit
    83				}
    84			}
    85			if len(frontier) == 0 {
    86				return nil, fmt.Errorf("no consistent ordering of events possible")
    87			}
    88			sort.Sort(orderEventList(frontier))
    89			f := frontier[0]
    90			frontier[0] = frontier[len(frontier)-1]
    91			frontier = frontier[:len(frontier)-1]
    92			events = append(events, f.ev)
    93			transition(gs, f.g, f.init, f.next)
    94			if !batches[f.batch].selected {
    95				panic("frontier batch is not selected")
    96			}
    97			batches[f.batch].selected = false
    98		}
    99	
   100		// At this point we have a consistent stream of events.
   101		// Make sure time stamps respect the ordering.
   102		// The tests will skip (not fail) the test case if they see this error.
   103		if !sort.IsSorted(eventList(events)) {
   104			return nil, ErrTimeOrder
   105		}
   106	
   107		// The last part is giving correct timestamps to EvGoSysExit events.
   108		// The problem with EvGoSysExit is that actual syscall exit timestamp (ev.Args[2])
   109		// is potentially acquired long before event emission. So far we've used
   110		// timestamp of event emission (ev.Ts).
   111		// We could not set ev.Ts = ev.Args[2] earlier, because it would produce
   112		// seemingly broken timestamps (misplaced event).
   113		// We also can't simply update the timestamp and resort events, because
   114		// if timestamps are broken we will misplace the event and later report
   115		// logically broken trace (instead of reporting broken timestamps).
   116		lastSysBlock := make(map[uint64]int64)
   117		for _, ev := range events {
   118			switch ev.Type {
   119			case EvGoSysBlock, EvGoInSyscall:
   120				lastSysBlock[ev.G] = ev.Ts
   121			case EvGoSysExit:
   122				ts := int64(ev.Args[2])
   123				if ts == 0 {
   124					continue
   125				}
   126				block := lastSysBlock[ev.G]
   127				if block == 0 {
   128					return nil, fmt.Errorf("stray syscall exit")
   129				}
   130				if ts < block {
   131					return nil, ErrTimeOrder
   132				}
   133				ev.Ts = ts
   134			}
   135		}
   136		sort.Stable(eventList(events))
   137	
   138		return
   139	}
   140	
   141	// stateTransition returns goroutine state (sequence and status) when the event
   142	// becomes ready for merging (init) and the goroutine state after the event (next).
   143	func stateTransition(ev *Event) (g uint64, init, next gState) {
   144		switch ev.Type {
   145		case EvGoCreate:
   146			g = ev.Args[0]
   147			init = gState{0, gDead}
   148			next = gState{1, gRunnable}
   149		case EvGoWaiting, EvGoInSyscall:
   150			g = ev.G
   151			init = gState{1, gRunnable}
   152			next = gState{2, gWaiting}
   153		case EvGoStart, EvGoStartLabel:
   154			g = ev.G
   155			init = gState{ev.Args[1], gRunnable}
   156			next = gState{ev.Args[1] + 1, gRunning}
   157		case EvGoStartLocal:
   158			// noseq means that this event is ready for merging as soon as
   159			// frontier reaches it (EvGoStartLocal is emitted on the same P
   160			// as the corresponding EvGoCreate/EvGoUnblock, and thus the latter
   161			// is already merged).
   162			// seqinc is a stub for cases when event increments g sequence,
   163			// but since we don't know current seq we also don't know next seq.
   164			g = ev.G
   165			init = gState{noseq, gRunnable}
   166			next = gState{seqinc, gRunning}
   167		case EvGoBlock, EvGoBlockSend, EvGoBlockRecv, EvGoBlockSelect,
   168			EvGoBlockSync, EvGoBlockCond, EvGoBlockNet, EvGoSleep,
   169			EvGoSysBlock, EvGoBlockGC:
   170			g = ev.G
   171			init = gState{noseq, gRunning}
   172			next = gState{noseq, gWaiting}
   173		case EvGoSched, EvGoPreempt:
   174			g = ev.G
   175			init = gState{noseq, gRunning}
   176			next = gState{noseq, gRunnable}
   177		case EvGoUnblock, EvGoSysExit:
   178			g = ev.Args[0]
   179			init = gState{ev.Args[1], gWaiting}
   180			next = gState{ev.Args[1] + 1, gRunnable}
   181		case EvGoUnblockLocal, EvGoSysExitLocal:
   182			g = ev.Args[0]
   183			init = gState{noseq, gWaiting}
   184			next = gState{seqinc, gRunnable}
   185		case EvGCStart:
   186			g = garbage
   187			init = gState{ev.Args[0], gDead}
   188			next = gState{ev.Args[0] + 1, gDead}
   189		default:
   190			// no ordering requirements
   191			g = unordered
   192		}
   193		return
   194	}
   195	
   196	func transitionReady(g uint64, curr, init gState) bool {
   197		return g == unordered || (init.seq == noseq || init.seq == curr.seq) && init.status == curr.status
   198	}
   199	
   200	func transition(gs map[uint64]gState, g uint64, init, next gState) {
   201		if g == unordered {
   202			return
   203		}
   204		curr := gs[g]
   205		if !transitionReady(g, curr, init) {
   206			panic("event sequences are broken")
   207		}
   208		switch next.seq {
   209		case noseq:
   210			next.seq = curr.seq
   211		case seqinc:
   212			next.seq = curr.seq + 1
   213		}
   214		gs[g] = next
   215	}
   216	
   217	// order1005 merges a set of per-P event batches into a single, consistent stream.
   218	func order1005(m map[int][]*Event) (events []*Event, err error) {
   219		for _, batch := range m {
   220			events = append(events, batch...)
   221		}
   222		for _, ev := range events {
   223			if ev.Type == EvGoSysExit {
   224				// EvGoSysExit emission is delayed until the thread has a P.
   225				// Give it the real sequence number and time stamp.
   226				ev.seq = int64(ev.Args[1])
   227				if ev.Args[2] != 0 {
   228					ev.Ts = int64(ev.Args[2])
   229				}
   230			}
   231		}
   232		sort.Sort(eventSeqList(events))
   233		if !sort.IsSorted(eventList(events)) {
   234			return nil, ErrTimeOrder
   235		}
   236		return
   237	}
   238	
   239	type orderEventList []orderEvent
   240	
   241	func (l orderEventList) Len() int {
   242		return len(l)
   243	}
   244	
   245	func (l orderEventList) Less(i, j int) bool {
   246		return l[i].ev.Ts < l[j].ev.Ts
   247	}
   248	
   249	func (l orderEventList) Swap(i, j int) {
   250		l[i], l[j] = l[j], l[i]
   251	}
   252	
   253	type eventList []*Event
   254	
   255	func (l eventList) Len() int {
   256		return len(l)
   257	}
   258	
   259	func (l eventList) Less(i, j int) bool {
   260		return l[i].Ts < l[j].Ts
   261	}
   262	
   263	func (l eventList) Swap(i, j int) {
   264		l[i], l[j] = l[j], l[i]
   265	}
   266	
   267	type eventSeqList []*Event
   268	
   269	func (l eventSeqList) Len() int {
   270		return len(l)
   271	}
   272	
   273	func (l eventSeqList) Less(i, j int) bool {
   274		return l[i].seq < l[j].seq
   275	}
   276	
   277	func (l eventSeqList) Swap(i, j int) {
   278		l[i], l[j] = l[j], l[i]
   279	}
   280	

View as plain text