runtime: add precise stack scan support

    
    This CL adds support of precise stack scan using stack maps to
    the runtime. The stack maps are generated by the compiler (if
    supported). Each safepoint is associated with a (real or dummy)
    landing pad, and its "type info" in the exception table is a
    pointer to the stack map. When a stack is scanned, the stack map
    is found by the stack unwinding code by inspecting the exception
    table (LSDA).
    
    For precise stack scan we need to unwind the stack. There are
    three cases:
    
    - If a goroutine is scanning its own stack, it can unwind the
      stack and scan the frames.
    
    - If a goroutine is scanning another, stopped, goroutine, it
      cannot directly unwind the target stack. We handle this by
      switching (runtime.gogo) to the target g, letting it unwind
      and scan the stack, and switch back.
    
    - If we are scanning a goroutine that is blocked in a syscall,
      we send a signal to the target goroutine's thread, and let the
      signal handler unwind and scan the stack. Extra care is needed
      as this races with enter/exit syscall.
    
    Currently this is only implemented on linux.
    
    Reviewed-on: https://go-review.googlesource.com/c/140518

From-SVN: r266832

8 files changed, 217 insertions, 8 deletions

diff --git a/libgo/go/runtime/mgcmark.go b/libgo/go/runtime/mgcmark.go
index 88cae414d40..631c4d7133b 100644
--- a/libgo/go/runtime/mgcmark.go
+++ b/libgo/go/runtime/mgcmark.go
@@ -664,7 +664,10 @@ func gcFlushBgCredit(scanWork int64) {
 }
 
 // We use a C function to find the stack.
-func doscanstack(*g, *gcWork)
+// Returns whether we succesfully scanned the stack.
+func doscanstack(*g, *gcWork) bool
+
+func doscanstackswitch(*g, *g)
 
 // scanstack scans gp's stack, greying all pointers found on the stack.
 //
@@ -691,7 +694,16 @@ func scanstack(gp *g, gcw *gcWork) {
 		return
 	case _Grunning:
 		// ok for gccgo, though not for gc.
-	case _Grunnable, _Gsyscall, _Gwaiting:
+		if usestackmaps {
+			print("runtime: gp=", gp, ", goid=", gp.goid, ", gp->atomicstatus=", readgstatus(gp), "\n")
+			throw("scanstack: goroutine not stopped")
+		}
+	case _Gsyscall:
+		if usestackmaps {
+			print("runtime: gp=", gp, ", goid=", gp.goid, ", gp->atomicstatus=", readgstatus(gp), "\n")
+			throw("scanstack: goroutine in syscall")
+		}
+	case _Grunnable, _Gwaiting:
 		// ok
 	}
 
@@ -701,15 +713,64 @@ func scanstack(gp *g, gcw *gcWork) {
 	}
 
 	// Scan the stack.
-	doscanstack(gp, gcw)
+	if usestackmaps {
+		g := getg()
+		if g == gp {
+			// Scan its own stack.
+			doscanstack(gp, gcw)
+		} else if gp.entry != nil {
+			// This is a newly created g that hasn't run. No stack to scan.
+		} else {
+			// Scanning another g's stack. We need to switch to that g
+			// to unwind its stack. And switch back after scan.
+			scanstackswitch(gp, gcw)
+		}
+	} else {
+		doscanstack(gp, gcw)
 
-	// Conservatively scan the saved register values.
-	scanstackblock(uintptr(unsafe.Pointer(&gp.gcregs)), unsafe.Sizeof(gp.gcregs), gcw)
-	scanstackblock(uintptr(unsafe.Pointer(&gp.context)), unsafe.Sizeof(gp.context), gcw)
+		// Conservatively scan the saved register values.
+		scanstackblock(uintptr(unsafe.Pointer(&gp.gcregs)), unsafe.Sizeof(gp.gcregs), gcw)
+		scanstackblock(uintptr(unsafe.Pointer(&gp.context)), unsafe.Sizeof(gp.context), gcw)
+	}
 
 	gp.gcscanvalid = true
 }
 
+// scanstackswitch scans gp's stack by switching (gogo) to gp and
+// letting it scan its own stack, and switching back upon finish.
+//
+//go:nowritebarrier
+func scanstackswitch(gp *g, gcw *gcWork) {
+	g := getg()
+
+	// We are on the system stack which prevents preemption. But
+	// we are going to switch to g stack. Lock m to block preemption.
+	mp := acquirem()
+
+	// The doscanstackswitch function will modify the current g's
+	// context. Preserve it.
+	// The stack scan code may call systemstack, which will modify
+	// gp's context. Preserve it as well so we can resume gp.
+	context := g.context
+	stackcontext := g.stackcontext
+	context2 := gp.context
+	stackcontext2 := gp.stackcontext
+
+	gp.scangcw = uintptr(unsafe.Pointer(gcw))
+	gp.scang = uintptr(unsafe.Pointer(g))
+	doscanstackswitch(g, gp)
+
+	// Restore the contexts.
+	g.context = context
+	g.stackcontext = stackcontext
+	gp.context = context2
+	gp.stackcontext = stackcontext2
+	gp.scangcw = 0
+	// gp.scang is already cleared in C code.
+
+	releasem(mp)
+}
+
 type gcDrainFlags int
 
 const (
@@ -1064,6 +1125,10 @@ func scanobject(b uintptr, gcw *gcWork) {
 // scanblock, but we scan the stack conservatively, so there is no
 // bitmask of pointers.
 func scanstackblock(b, n uintptr, gcw *gcWork) {
+	if usestackmaps {
+		throw("scanstackblock: conservative scan but stack map is used")
+	}
+
 	for i := uintptr(0); i < n; i += sys.PtrSize {
 		// Same work as in scanobject; see comments there.
 		obj := *(*uintptr)(unsafe.Pointer(b + i))
@@ -1073,6 +1138,50 @@ func scanstackblock(b, n uintptr, gcw *gcWork) {
 	}
 }
 
+// scanstackblockwithmap is like scanstackblock, but with an explicit
+// pointer bitmap. This is used only when precise stack scan is enabled.
+//go:linkname scanstackblockwithmap runtime.scanstackblockwithmap
+//go:nowritebarrier
+func scanstackblockwithmap(pc, b0, n0 uintptr, ptrmask *uint8, gcw *gcWork) {
+	// Use local copies of original parameters, so that a stack trace
+	// due to one of the throws below shows the original block
+	// base and extent.
+	b := b0
+	n := n0
+
+	for i := uintptr(0); i < n; {
+		// Find bits for the next word.
+		bits := uint32(*addb(ptrmask, i/(sys.PtrSize*8)))
+		if bits == 0 {
+			i += sys.PtrSize * 8
+			continue
+		}
+		for j := 0; j < 8 && i < n; j++ {
+			if bits&1 != 0 {
+				// Same work as in scanobject; see comments there.
+				obj := *(*uintptr)(unsafe.Pointer(b + i))
+				if obj != 0 {
+					o, span, objIndex := findObject(obj, b, i, false)
+					if obj < minPhysPageSize ||
+						span != nil && span.state != _MSpanManual &&
+							(obj < span.base() || obj >= span.limit || span.state != mSpanInUse) {
+						print("runtime: found in object at *(", hex(b), "+", hex(i), ") = ", hex(obj), ", pc=", hex(pc), "\n")
+						name, file, line := funcfileline(pc, -1)
+						print(name, "\n", file, ":", line, "\n")
+						//gcDumpObject("object", b, i)
+						throw("found bad pointer in Go stack (incorrect use of unsafe or cgo?)")
+					}
+					if o != 0 {
+						greyobject(o, b, i, span, gcw, objIndex, false)
+					}
+				}
+			}
+			bits >>= 1
+			i += sys.PtrSize
+		}
+	}
+}
+
 // Shade the object if it isn't already.
 // The object is not nil and known to be in the heap.
 // Preemption must be disabled.
diff --git a/libgo/go/runtime/os_gccgo.go b/libgo/go/runtime/os_gccgo.go
index 5709555acdb..08511fd2aca 100644
--- a/libgo/go/runtime/os_gccgo.go
+++ b/libgo/go/runtime/os_gccgo.go
@@ -27,7 +27,8 @@ func mpreinit(mp *m) {
 func minit() {
 	minitSignals()
 
-	// FIXME: We should set _g_.m.procid here.
+	// FIXME: only works on linux for now.
+	getg().m.procid = uint64(gettid())
 }
 
 // Called from dropm to undo the effect of an minit.
diff --git a/libgo/go/runtime/proc.go b/libgo/go/runtime/proc.go
index bb16924e01c..ef166cb9d28 100644
--- a/libgo/go/runtime/proc.go
+++ b/libgo/go/runtime/proc.go
@@ -528,6 +528,8 @@ func schedinit() {
 
 	sched.maxmcount = 10000
 
+	usestackmaps = probestackmaps()
+
 	mallocinit()
 	mcommoninit(_g_.m)
 	cpuinit() // must run before alginit
@@ -891,7 +893,49 @@ loop:
 		case _Gcopystack:
 		// Stack being switched. Go around again.
 
-		case _Grunnable, _Gsyscall, _Gwaiting:
+		case _Gsyscall:
+			if usestackmaps {
+				// Claim goroutine by setting scan bit.
+				// Racing with execution or readying of gp.
+				// The scan bit keeps them from running
+				// the goroutine until we're done.
+				if castogscanstatus(gp, s, s|_Gscan) {
+					if gp.scanningself {
+						// Don't try to scan the stack
+						// if the goroutine is going to do
+						// it itself.
+						// FIXME: can this happen?
+						restartg(gp)
+						break
+					}
+					if !gp.gcscandone {
+						// Send a signal to let the goroutine scan
+						// itself. This races with enter/exitsyscall.
+						// If the goroutine is not stopped at a safepoint,
+						// it will not scan the stack and we'll try again.
+						mp := gp.m
+						noteclear(&mp.scannote)
+						gp.scangcw = uintptr(unsafe.Pointer(gcw))
+						tgkill(getpid(), _pid_t(mp.procid), _SIGURG)
+
+						// Wait for gp to scan its own stack.
+						notesleep(&mp.scannote)
+
+						if !gp.gcscandone {
+							// The signal delivered at a bad time.
+							// Try again.
+							restartg(gp)
+							break
+						}
+					}
+					restartg(gp)
+					break loop
+				}
+				break
+			}
+			fallthrough
+
+		case _Grunnable, _Gwaiting:
 			// Claim goroutine by setting scan bit.
 			// Racing with execution or readying of gp.
 			// The scan bit keeps them from running
@@ -954,6 +998,11 @@ loop:
 
 // The GC requests that this routine be moved from a scanmumble state to a mumble state.
 func restartg(gp *g) {
+	if gp.scang != 0 || gp.scangcw != 0 {
+		print("g ", gp.goid, "is being scanned scang=", gp.scang, " scangcw=", gp.scangcw, "\n")
+		throw("restartg: being scanned")
+	}
+
 	s := readgstatus(gp)
 	switch s {
 	default:
diff --git a/libgo/go/runtime/runtime2.go b/libgo/go/runtime/runtime2.go
index e12e832c14a..6eb9491018d 100644
--- a/libgo/go/runtime/runtime2.go
+++ b/libgo/go/runtime/runtime2.go
@@ -430,6 +430,9 @@ type g struct {
 
 	scanningself bool // whether goroutine is scanning its own stack
 
+	scang   uintptr // the g that wants to scan this g's stack (uintptr to avoid write barrier)
+	scangcw uintptr // gc worker for scanning stack (uintptr to avoid write barrier)
+
 	isSystemGoroutine bool // whether goroutine is a "system" goroutine
 
 	traceback uintptr // stack traceback buffer
@@ -514,6 +517,8 @@ type m struct {
 	exiting    bool // thread is exiting
 
 	gcing int32
+
+	scannote note // synchonization for signal-based stack scanning
 }
 
 type p struct {
diff --git a/libgo/go/runtime/signal_sighandler.go b/libgo/go/runtime/signal_sighandler.go
index e4bf7bc4426..b41eaf40970 100644
--- a/libgo/go/runtime/signal_sighandler.go
+++ b/libgo/go/runtime/signal_sighandler.go
@@ -36,6 +36,28 @@ func sighandler(sig uint32, info *_siginfo_t, ctxt unsafe.Pointer, gp *g) {
 
 	sigfault, sigpc := getSiginfo(info, ctxt)
 
+	if sig == _SIGURG && usestackmaps {
+		// We may be signaled to do a stack scan.
+		// The signal delivery races with enter/exitsyscall.
+		// We may be on g0 stack now. gp.m.curg is the g we
+		// want to scan.
+		// If we're not on g stack, give up. The sender will
+		// try again later.
+		// If we're not stopped at a safepoint (doscanstack will
+		// return false), also give up.
+		if s := readgstatus(gp.m.curg); s == _Gscansyscall {
+			if gp == gp.m.curg {
+				if doscanstack(gp, (*gcWork)(unsafe.Pointer(gp.scangcw))) {
+					gp.gcscanvalid = true
+					gp.gcscandone = true
+				}
+			}
+			gp.m.curg.scangcw = 0
+			notewakeup(&gp.m.scannote)
+			return
+		}
+	}
+
 	if sig == _SIGPROF {
 		sigprof(sigpc, gp, _g_.m)
 		return
diff --git a/libgo/go/runtime/stubs.go b/libgo/go/runtime/stubs.go
index 1aae4f30245..4caa39d5e94 100644
--- a/libgo/go/runtime/stubs.go
+++ b/libgo/go/runtime/stubs.go
@@ -447,3 +447,10 @@ func bool2int(x bool) int {
 // signal handler, which will attempt to tear down the runtime
 // immediately.
 func abort()
+
+// usestackmaps is true if stack map (precise stack scan) is enabled.
+var usestackmaps bool
+
+// probestackmaps detects whether there are stack maps.
+//go:linkname probestackmaps runtime.probestackmaps
+func probestackmaps() bool
diff --git a/libgo/go/runtime/stubs_linux.go b/libgo/go/runtime/stubs_linux.go
index d10f657197f..3c733e37d9a 100644
--- a/libgo/go/runtime/stubs_linux.go
+++ b/libgo/go/runtime/stubs_linux.go
@@ -7,3 +7,11 @@
 package runtime
 
 func sbrk0() uintptr
+
+func gettid() _pid_t {
+	return _pid_t(syscall(_SYS_gettid, 0, 0, 0, 0, 0, 0))
+}
+
+func tgkill(pid _pid_t, tid _pid_t, sig uint32) uint32 {
+	return uint32(syscall(_SYS_tgkill, uintptr(pid), uintptr(tid), uintptr(sig), 0, 0, 0))
+}
diff --git a/libgo/go/runtime/stubs_nonlinux.go b/libgo/go/runtime/stubs_nonlinux.go
index e1ea05cf0b1..4cdab0c8b81 100644
--- a/libgo/go/runtime/stubs_nonlinux.go
+++ b/libgo/go/runtime/stubs_nonlinux.go
@@ -10,3 +10,11 @@ package runtime
 func sbrk0() uintptr {
 	return 0
 }
+
+func gettid() _pid_t {
+	return 0
+}
+
+func tgkill(pid _pid_t, tid _pid_t, sig uint32) uint32 {
+	throw("tgkill not implemented")
+}