runtime: break out system-specific constants into package sys

[gostls13.git] / src / runtime / mstkbar.go

// Copyright 2015 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.

// Garbage collector: stack barriers
//
// Stack barriers enable the garbage collector to determine how much
// of a gorountine stack has changed between when a stack is scanned
// during the concurrent scan phase and when it is re-scanned during
// the stop-the-world mark termination phase. Mark termination only
// needs to re-scan the changed part, so for deep stacks this can
// significantly reduce GC pause time compared to the alternative of
// re-scanning whole stacks. The deeper the stacks, the more stack
// barriers help.
//
// When stacks are scanned during the concurrent scan phase, the stack
// scan installs stack barriers by selecting stack frames and
// overwriting the saved return PCs (or link registers) of these
// frames with the PC of a "stack barrier trampoline". Later, when a
// selected frame returns, it "returns" to this trampoline instead of
// returning to its actual caller. The trampoline records that the
// stack has unwound past this frame and jumps to the original return
// PC recorded when the stack barrier was installed. Mark termination
// re-scans only as far as the first frame that hasn't hit a stack
// barrier and then removes and un-hit stack barriers.
//
// This scheme is very lightweight. No special code is required in the
// mutator to record stack unwinding and the trampoline is only a few
// assembly instructions.
//
// Book-keeping
// ------------
//
// The primary cost of stack barriers is book-keeping: the runtime has
// to record the locations of all stack barriers and the original
// return PCs in order to return to the correct caller when a stack
// barrier is hit and so it can remove un-hit stack barriers. In order
// to minimize this cost, the Go runtime places stack barriers in
// exponentially-spaced frames, starting 1K past the current frame.
// The book-keeping structure hence grows logarithmically with the
// size of the stack and mark termination re-scans at most twice as
// much stack as necessary.
//
// The runtime reserves space for this book-keeping structure at the
// top of the stack allocation itself (just above the outermost
// frame). This is necessary because the regular memory allocator can
// itself grow the stack, and hence can't be used when allocating
// stack-related structures.
//
// For debugging, the runtime also supports installing stack barriers
// at every frame. However, this requires significantly more
// book-keeping space.
//
// Correctness
// -----------
//
// The runtime and the compiler cooperate to ensure that all objects
// reachable from the stack as of mark termination are marked.
// Anything unchanged since the concurrent scan phase will be marked
// because it is marked by the concurrent scan. After the concurrent
// scan, there are three possible classes of stack modifications that
// must be tracked:
//
// 1) Mutator writes below the lowest un-hit stack barrier. This
// includes all writes performed by an executing function to its own
// stack frame. This part of the stack will be re-scanned by mark
// termination, which will mark any objects made reachable from
// modifications to this part of the stack.
//
// 2) Mutator writes above the lowest un-hit stack barrier. It's
// possible for a mutator to modify the stack above the lowest un-hit
// stack barrier if a higher frame has passed down a pointer to a
// stack variable in its frame. This is called an "up-pointer". The
// compiler ensures that writes through up-pointers have an
// accompanying write barrier (it simply doesn't distinguish between
// writes through up-pointers and writes through heap pointers). This
// write barrier marks any object made reachable from modifications to
// this part of the stack.
//
// 3) Runtime writes to the stack. Various runtime operations such as
// sends to unbuffered channels can write to arbitrary parts of the
// stack, including above the lowest un-hit stack barrier. We solve
// this in two ways. In many cases, the runtime can perform an
// explicit write barrier operation like in case 2. However, in the
// case of bulk memory move (typedmemmove), the runtime doesn't
// necessary have ready access to a pointer bitmap for the memory
// being copied, so it simply unwinds any stack barriers below the
// destination.
//
// Gotchas
// -------
//
// Anything that inspects or manipulates the stack potentially needs
// to understand stack barriers. The most obvious case is that
// gentraceback needs to use the original return PC when it encounters
// the stack barrier trampoline. Anything that unwinds the stack such
// as panic/recover must unwind stack barriers in tandem with
// unwinding the stack.
//
// Stack barriers require that any goroutine whose stack has been
// scanned must execute write barriers. Go solves this by simply
// enabling write barriers globally during the concurrent scan phase.
// However, traditionally, write barriers are not enabled during this
// phase.

package runtime

import (
        "runtime/internal/sys"
        "unsafe"
)

const debugStackBarrier = false

// firstStackBarrierOffset is the approximate byte offset at
// which to place the first stack barrier from the current SP.
// This is a lower bound on how much stack will have to be
// re-scanned during mark termination. Subsequent barriers are
// placed at firstStackBarrierOffset * 2^n offsets.
//
// For debugging, this can be set to 0, which will install a
// stack barrier at every frame. If you do this, you may also
// have to raise _StackMin, since the stack barrier
// bookkeeping will use a large amount of each stack.
var firstStackBarrierOffset = 1024

// gcMaxStackBarriers returns the maximum number of stack barriers
// that can be installed in a stack of stackSize bytes.
func gcMaxStackBarriers(stackSize int) (n int) {
        if firstStackBarrierOffset == 0 {
                // Special debugging case for inserting stack barriers
                // at every frame. Steal half of the stack for the
                // []stkbar. Technically, if the stack were to consist
                // solely of return PCs we would need two thirds of
                // the stack, but stealing that much breaks things and
                // this doesn't happen in practice.
                return stackSize / 2 / int(unsafe.Sizeof(stkbar{}))
        }

        offset := firstStackBarrierOffset
        for offset < stackSize {
                n++
                offset *= 2
        }
        return n + 1
}

// gcInstallStackBarrier installs a stack barrier over the return PC of frame.
//go:nowritebarrier
func gcInstallStackBarrier(gp *g, frame *stkframe) bool {
        if frame.lr == 0 {
                if debugStackBarrier {
                        print("not installing stack barrier with no LR, goid=", gp.goid, "\n")
                }
                return false
        }

        if frame.fn.entry == cgocallback_gofuncPC {
                // cgocallback_gofunc doesn't return to its LR;
                // instead, its return path puts LR in g.sched.pc and
                // switches back to the system stack on which
                // cgocallback_gofunc was originally called. We can't
                // have a stack barrier in g.sched.pc, so don't
                // install one in this frame.
                if debugStackBarrier {
                        print("not installing stack barrier over LR of cgocallback_gofunc, goid=", gp.goid, "\n")
                }
                return false
        }

        // Save the return PC and overwrite it with stackBarrier.
        var lrUintptr uintptr
        if usesLR {
                lrUintptr = frame.sp
        } else {
                lrUintptr = frame.fp - sys.RegSize
        }
        lrPtr := (*sys.Uintreg)(unsafe.Pointer(lrUintptr))
        if debugStackBarrier {
                print("install stack barrier at ", hex(lrUintptr), " over ", hex(*lrPtr), ", goid=", gp.goid, "\n")
                if uintptr(*lrPtr) != frame.lr {
                        print("frame.lr=", hex(frame.lr))
                        throw("frame.lr differs from stack LR")
                }
        }

        gp.stkbar = gp.stkbar[:len(gp.stkbar)+1]
        stkbar := &gp.stkbar[len(gp.stkbar)-1]
        stkbar.savedLRPtr = lrUintptr
        stkbar.savedLRVal = uintptr(*lrPtr)
        *lrPtr = sys.Uintreg(stackBarrierPC)
        return true
}

// gcRemoveStackBarriers removes all stack barriers installed in gp's stack.
//go:nowritebarrier
func gcRemoveStackBarriers(gp *g) {
        if debugStackBarrier && gp.stkbarPos != 0 {
                print("hit ", gp.stkbarPos, " stack barriers, goid=", gp.goid, "\n")
        }

        // Remove stack barriers that we didn't hit.
        for _, stkbar := range gp.stkbar[gp.stkbarPos:] {
                gcRemoveStackBarrier(gp, stkbar)
        }

        // Clear recorded stack barriers so copystack doesn't try to
        // adjust them.
        gp.stkbarPos = 0
        gp.stkbar = gp.stkbar[:0]
}

// gcRemoveStackBarrier removes a single stack barrier. It is the
// inverse operation of gcInstallStackBarrier.
//
// This is nosplit to ensure gp's stack does not move.
//
//go:nowritebarrier
//go:nosplit
func gcRemoveStackBarrier(gp *g, stkbar stkbar) {
        if debugStackBarrier {
                print("remove stack barrier at ", hex(stkbar.savedLRPtr), " with ", hex(stkbar.savedLRVal), ", goid=", gp.goid, "\n")
        }
        lrPtr := (*sys.Uintreg)(unsafe.Pointer(stkbar.savedLRPtr))
        if val := *lrPtr; val != sys.Uintreg(stackBarrierPC) {
                printlock()
                print("at *", hex(stkbar.savedLRPtr), " expected stack barrier PC ", hex(stackBarrierPC), ", found ", hex(val), ", goid=", gp.goid, "\n")
                print("gp.stkbar=")
                gcPrintStkbars(gp.stkbar)
                print(", gp.stkbarPos=", gp.stkbarPos, ", gp.stack=[", hex(gp.stack.lo), ",", hex(gp.stack.hi), ")\n")
                throw("stack barrier lost")
        }
        *lrPtr = sys.Uintreg(stkbar.savedLRVal)
}

// gcPrintStkbars prints a []stkbar for debugging.
func gcPrintStkbars(stkbar []stkbar) {
        print("[")
        for i, s := range stkbar {
                if i > 0 {
                        print(" ")
                }
                print("*", hex(s.savedLRPtr), "=", hex(s.savedLRVal))
        }
        print("]")
}

// gcUnwindBarriers marks all stack barriers up the frame containing
// sp as hit and removes them. This is used during stack unwinding for
// panic/recover and by heapBitsBulkBarrier to force stack re-scanning
// when its destination is on the stack.
//
// This is nosplit to ensure gp's stack does not move.
//
//go:nosplit
func gcUnwindBarriers(gp *g, sp uintptr) {
        // On LR machines, if there is a stack barrier on the return
        // from the frame containing sp, this will mark it as hit even
        // though it isn't, but it's okay to be conservative.
        before := gp.stkbarPos
        for int(gp.stkbarPos) < len(gp.stkbar) && gp.stkbar[gp.stkbarPos].savedLRPtr < sp {
                gcRemoveStackBarrier(gp, gp.stkbar[gp.stkbarPos])
                gp.stkbarPos++
        }
        if debugStackBarrier && gp.stkbarPos != before {
                print("skip barriers below ", hex(sp), " in goid=", gp.goid, ": ")
                gcPrintStkbars(gp.stkbar[before:gp.stkbarPos])
                print("\n")
        }
}

// nextBarrierPC returns the original return PC of the next stack barrier.
// Used by getcallerpc, so it must be nosplit.
//go:nosplit
func nextBarrierPC() uintptr {
        gp := getg()
        return gp.stkbar[gp.stkbarPos].savedLRVal
}

// setNextBarrierPC sets the return PC of the next stack barrier.
// Used by setcallerpc, so it must be nosplit.
//go:nosplit
func setNextBarrierPC(pc uintptr) {
        gp := getg()
        gp.stkbar[gp.stkbarPos].savedLRVal = pc
}