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