2018-23-01 Paul Thomas <pault@gcc.gnu.org>

[official-gcc.git] / libgo / go / runtime / mgcwork.go

// Copyright 2009 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 runtime

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

const (
        _WorkbufSize = 2048 // in bytes; larger values result in less contention

        // workbufAlloc is the number of bytes to allocate at a time
        // for new workbufs. This must be a multiple of pageSize and
        // should be a multiple of _WorkbufSize.
        //
        // Larger values reduce workbuf allocation overhead. Smaller
        // values reduce heap fragmentation.
        workbufAlloc = 32 << 10
)

func init() {
        if workbufAlloc%pageSize != 0 || workbufAlloc%_WorkbufSize != 0 {
                throw("bad workbufAlloc")
        }
}

// Garbage collector work pool abstraction.
//
// This implements a producer/consumer model for pointers to grey
// objects. A grey object is one that is marked and on a work
// queue. A black object is marked and not on a work queue.
//
// Write barriers, root discovery, stack scanning, and object scanning
// produce pointers to grey objects. Scanning consumes pointers to
// grey objects, thus blackening them, and then scans them,
// potentially producing new pointers to grey objects.

// A gcWork provides the interface to produce and consume work for the
// garbage collector.
//
// A gcWork can be used on the stack as follows:
//
//     (preemption must be disabled)
//     gcw := &getg().m.p.ptr().gcw
//     .. call gcw.put() to produce and gcw.get() to consume ..
//     if gcBlackenPromptly {
//         gcw.dispose()
//     }
//
// It's important that any use of gcWork during the mark phase prevent
// the garbage collector from transitioning to mark termination since
// gcWork may locally hold GC work buffers. This can be done by
// disabling preemption (systemstack or acquirem).
type gcWork struct {
        // wbuf1 and wbuf2 are the primary and secondary work buffers.
        //
        // This can be thought of as a stack of both work buffers'
        // pointers concatenated. When we pop the last pointer, we
        // shift the stack up by one work buffer by bringing in a new
        // full buffer and discarding an empty one. When we fill both
        // buffers, we shift the stack down by one work buffer by
        // bringing in a new empty buffer and discarding a full one.
        // This way we have one buffer's worth of hysteresis, which
        // amortizes the cost of getting or putting a work buffer over
        // at least one buffer of work and reduces contention on the
        // global work lists.
        //
        // wbuf1 is always the buffer we're currently pushing to and
        // popping from and wbuf2 is the buffer that will be discarded
        // next.
        //
        // Invariant: Both wbuf1 and wbuf2 are nil or neither are.
        wbuf1, wbuf2 *workbuf

        // Bytes marked (blackened) on this gcWork. This is aggregated
        // into work.bytesMarked by dispose.
        bytesMarked uint64

        // Scan work performed on this gcWork. This is aggregated into
        // gcController by dispose and may also be flushed by callers.
        scanWork int64
}

// Most of the methods of gcWork are go:nowritebarrierrec because the
// write barrier itself can invoke gcWork methods but the methods are
// not generally re-entrant. Hence, if a gcWork method invoked the
// write barrier while the gcWork was in an inconsistent state, and
// the write barrier in turn invoked a gcWork method, it could
// permanently corrupt the gcWork.

func (w *gcWork) init() {
        w.wbuf1 = getempty()
        wbuf2 := trygetfull()
        if wbuf2 == nil {
                wbuf2 = getempty()
        }
        w.wbuf2 = wbuf2
}

// put enqueues a pointer for the garbage collector to trace.
// obj must point to the beginning of a heap object or an oblet.
//go:nowritebarrierrec
func (w *gcWork) put(obj uintptr) {
        flushed := false
        wbuf := w.wbuf1
        if wbuf == nil {
                w.init()
                wbuf = w.wbuf1
                // wbuf is empty at this point.
        } else if wbuf.nobj == len(wbuf.obj) {
                w.wbuf1, w.wbuf2 = w.wbuf2, w.wbuf1
                wbuf = w.wbuf1
                if wbuf.nobj == len(wbuf.obj) {
                        putfull(wbuf)
                        wbuf = getempty()
                        w.wbuf1 = wbuf
                        flushed = true
                }
        }

        wbuf.obj[wbuf.nobj] = obj
        wbuf.nobj++

        // If we put a buffer on full, let the GC controller know so
        // it can encourage more workers to run. We delay this until
        // the end of put so that w is in a consistent state, since
        // enlistWorker may itself manipulate w.
        if flushed && gcphase == _GCmark {
                gcController.enlistWorker()
        }
}

// putFast does a put and returns true if it can be done quickly
// otherwise it returns false and the caller needs to call put.
//go:nowritebarrierrec
func (w *gcWork) putFast(obj uintptr) bool {
        wbuf := w.wbuf1
        if wbuf == nil {
                return false
        } else if wbuf.nobj == len(wbuf.obj) {
                return false
        }

        wbuf.obj[wbuf.nobj] = obj
        wbuf.nobj++
        return true
}

// putBatch performs a put on every pointer in obj. See put for
// constraints on these pointers.
//
//go:nowritebarrierrec
func (w *gcWork) putBatch(obj []uintptr) {
        if len(obj) == 0 {
                return
        }

        flushed := false
        wbuf := w.wbuf1
        if wbuf == nil {
                w.init()
                wbuf = w.wbuf1
        }

        for len(obj) > 0 {
                for wbuf.nobj == len(wbuf.obj) {
                        putfull(wbuf)
                        w.wbuf1, w.wbuf2 = w.wbuf2, getempty()
                        wbuf = w.wbuf1
                        flushed = true
                }
                n := copy(wbuf.obj[wbuf.nobj:], obj)
                wbuf.nobj += n
                obj = obj[n:]
        }

        if flushed && gcphase == _GCmark {
                gcController.enlistWorker()
        }
}

// tryGet dequeues a pointer for the garbage collector to trace.
//
// If there are no pointers remaining in this gcWork or in the global
// queue, tryGet returns 0.  Note that there may still be pointers in
// other gcWork instances or other caches.
//go:nowritebarrierrec
func (w *gcWork) tryGet() uintptr {
        wbuf := w.wbuf1
        if wbuf == nil {
                w.init()
                wbuf = w.wbuf1
                // wbuf is empty at this point.
        }
        if wbuf.nobj == 0 {
                w.wbuf1, w.wbuf2 = w.wbuf2, w.wbuf1
                wbuf = w.wbuf1
                if wbuf.nobj == 0 {
                        owbuf := wbuf
                        wbuf = trygetfull()
                        if wbuf == nil {
                                return 0
                        }
                        putempty(owbuf)
                        w.wbuf1 = wbuf
                }
        }

        wbuf.nobj--
        return wbuf.obj[wbuf.nobj]
}

// tryGetFast dequeues a pointer for the garbage collector to trace
// if one is readily available. Otherwise it returns 0 and
// the caller is expected to call tryGet().
//go:nowritebarrierrec
func (w *gcWork) tryGetFast() uintptr {
        wbuf := w.wbuf1
        if wbuf == nil {
                return 0
        }
        if wbuf.nobj == 0 {
                return 0
        }

        wbuf.nobj--
        return wbuf.obj[wbuf.nobj]
}

// get dequeues a pointer for the garbage collector to trace, blocking
// if necessary to ensure all pointers from all queues and caches have
// been retrieved.  get returns 0 if there are no pointers remaining.
//go:nowritebarrierrec
func (w *gcWork) get() uintptr {
        wbuf := w.wbuf1
        if wbuf == nil {
                w.init()
                wbuf = w.wbuf1
                // wbuf is empty at this point.
        }
        if wbuf.nobj == 0 {
                w.wbuf1, w.wbuf2 = w.wbuf2, w.wbuf1
                wbuf = w.wbuf1
                if wbuf.nobj == 0 {
                        owbuf := wbuf
                        wbuf = getfull()
                        if wbuf == nil {
                                return 0
                        }
                        putempty(owbuf)
                        w.wbuf1 = wbuf
                }
        }

        // TODO: This might be a good place to add prefetch code

        wbuf.nobj--
        return wbuf.obj[wbuf.nobj]
}

// dispose returns any cached pointers to the global queue.
// The buffers are being put on the full queue so that the
// write barriers will not simply reacquire them before the
// GC can inspect them. This helps reduce the mutator's
// ability to hide pointers during the concurrent mark phase.
//
//go:nowritebarrierrec
func (w *gcWork) dispose() {
        if wbuf := w.wbuf1; wbuf != nil {
                if wbuf.nobj == 0 {
                        putempty(wbuf)
                } else {
                        putfull(wbuf)
                }
                w.wbuf1 = nil

                wbuf = w.wbuf2
                if wbuf.nobj == 0 {
                        putempty(wbuf)
                } else {
                        putfull(wbuf)
                }
                w.wbuf2 = nil
        }
        if w.bytesMarked != 0 {
                // dispose happens relatively infrequently. If this
                // atomic becomes a problem, we should first try to
                // dispose less and if necessary aggregate in a per-P
                // counter.
                atomic.Xadd64(&work.bytesMarked, int64(w.bytesMarked))
                w.bytesMarked = 0
        }
        if w.scanWork != 0 {
                atomic.Xaddint64(&gcController.scanWork, w.scanWork)
                w.scanWork = 0
        }
}

// balance moves some work that's cached in this gcWork back on the
// global queue.
//go:nowritebarrierrec
func (w *gcWork) balance() {
        if w.wbuf1 == nil {
                return
        }
        if wbuf := w.wbuf2; wbuf.nobj != 0 {
                putfull(wbuf)
                w.wbuf2 = getempty()
        } else if wbuf := w.wbuf1; wbuf.nobj > 4 {
                w.wbuf1 = handoff(wbuf)
        } else {
                return
        }
        // We flushed a buffer to the full list, so wake a worker.
        if gcphase == _GCmark {
                gcController.enlistWorker()
        }
}

// empty returns true if w has no mark work available.
//go:nowritebarrierrec
func (w *gcWork) empty() bool {
        return w.wbuf1 == nil || (w.wbuf1.nobj == 0 && w.wbuf2.nobj == 0)
}

// Internally, the GC work pool is kept in arrays in work buffers.
// The gcWork interface caches a work buffer until full (or empty) to
// avoid contending on the global work buffer lists.

type workbufhdr struct {
        node lfnode // must be first
        nobj int
}

//go:notinheap
type workbuf struct {
        workbufhdr
        // account for the above fields
        obj [(_WorkbufSize - unsafe.Sizeof(workbufhdr{})) / sys.PtrSize]uintptr
}

// workbuf factory routines. These funcs are used to manage the
// workbufs.
// If the GC asks for some work these are the only routines that
// make wbufs available to the GC.

func (b *workbuf) checknonempty() {
        if b.nobj == 0 {
                throw("workbuf is empty")
        }
}

func (b *workbuf) checkempty() {
        if b.nobj != 0 {
                throw("workbuf is not empty")
        }
}

// getempty pops an empty work buffer off the work.empty list,
// allocating new buffers if none are available.
//go:nowritebarrier
func getempty() *workbuf {
        var b *workbuf
        if work.empty != 0 {
                b = (*workbuf)(work.empty.pop())
                if b != nil {
                        b.checkempty()
                }
        }
        if b == nil {
                // Allocate more workbufs.
                var s *mspan
                if work.wbufSpans.free.first != nil {
                        lock(&work.wbufSpans.lock)
                        s = work.wbufSpans.free.first
                        if s != nil {
                                work.wbufSpans.free.remove(s)
                                work.wbufSpans.busy.insert(s)
                        }
                        unlock(&work.wbufSpans.lock)
                }
                if s == nil {
                        systemstack(func() {
                                s = mheap_.allocManual(workbufAlloc/pageSize, &memstats.gc_sys)
                        })
                        if s == nil {
                                throw("out of memory")
                        }
                        // Record the new span in the busy list.
                        lock(&work.wbufSpans.lock)
                        work.wbufSpans.busy.insert(s)
                        unlock(&work.wbufSpans.lock)
                }
                // Slice up the span into new workbufs. Return one and
                // put the rest on the empty list.
                for i := uintptr(0); i+_WorkbufSize <= workbufAlloc; i += _WorkbufSize {
                        newb := (*workbuf)(unsafe.Pointer(s.base() + i))
                        newb.nobj = 0
                        if i == 0 {
                                b = newb
                        } else {
                                putempty(newb)
                        }
                }
        }
        return b
}

// putempty puts a workbuf onto the work.empty list.
// Upon entry this go routine owns b. The lfstack.push relinquishes ownership.
//go:nowritebarrier
func putempty(b *workbuf) {
        b.checkempty()
        work.empty.push(&b.node)
}

// putfull puts the workbuf on the work.full list for the GC.
// putfull accepts partially full buffers so the GC can avoid competing
// with the mutators for ownership of partially full buffers.
//go:nowritebarrier
func putfull(b *workbuf) {
        b.checknonempty()
        work.full.push(&b.node)
}

// trygetfull tries to get a full or partially empty workbuffer.
// If one is not immediately available return nil
//go:nowritebarrier
func trygetfull() *workbuf {
        b := (*workbuf)(work.full.pop())
        if b != nil {
                b.checknonempty()
                return b
        }
        return b
}

// Get a full work buffer off the work.full list.
// If nothing is available wait until all the other gc helpers have
// finished and then return nil.
// getfull acts as a barrier for work.nproc helpers. As long as one
// gchelper is actively marking objects it
// may create a workbuffer that the other helpers can work on.
// The for loop either exits when a work buffer is found
// or when _all_ of the work.nproc GC helpers are in the loop
// looking for work and thus not capable of creating new work.
// This is in fact the termination condition for the STW mark
// phase.
//go:nowritebarrier
func getfull() *workbuf {
        b := (*workbuf)(work.full.pop())
        if b != nil {
                b.checknonempty()
                return b
        }

        incnwait := atomic.Xadd(&work.nwait, +1)
        if incnwait > work.nproc {
                println("runtime: work.nwait=", incnwait, "work.nproc=", work.nproc)
                throw("work.nwait > work.nproc")
        }
        for i := 0; ; i++ {
                if work.full != 0 {
                        decnwait := atomic.Xadd(&work.nwait, -1)
                        if decnwait == work.nproc {
                                println("runtime: work.nwait=", decnwait, "work.nproc=", work.nproc)
                                throw("work.nwait > work.nproc")
                        }
                        b = (*workbuf)(work.full.pop())
                        if b != nil {
                                b.checknonempty()
                                return b
                        }
                        incnwait := atomic.Xadd(&work.nwait, +1)
                        if incnwait > work.nproc {
                                println("runtime: work.nwait=", incnwait, "work.nproc=", work.nproc)
                                throw("work.nwait > work.nproc")
                        }
                }
                if work.nwait == work.nproc && work.markrootNext >= work.markrootJobs {
                        return nil
                }
                if i < 10 {
                        procyield(20)
                } else if i < 20 {
                        osyield()
                } else {
                        usleep(100)
                }
        }
}

//go:nowritebarrier
func handoff(b *workbuf) *workbuf {
        // Make new buffer with half of b's pointers.
        b1 := getempty()
        n := b.nobj / 2
        b.nobj -= n
        b1.nobj = n
        memmove(unsafe.Pointer(&b1.obj[0]), unsafe.Pointer(&b.obj[b.nobj]), uintptr(n)*unsafe.Sizeof(b1.obj[0]))

        // Put b on full list - let first half of b get stolen.
        putfull(b)
        return b1
}

// prepareFreeWorkbufs moves busy workbuf spans to free list so they
// can be freed to the heap. This must only be called when all
// workbufs are on the empty list.
func prepareFreeWorkbufs() {
        lock(&work.wbufSpans.lock)
        if work.full != 0 {
                throw("cannot free workbufs when work.full != 0")
        }
        // Since all workbufs are on the empty list, we don't care
        // which ones are in which spans. We can wipe the entire empty
        // list and move all workbuf spans to the free list.
        work.empty = 0
        work.wbufSpans.free.takeAll(&work.wbufSpans.busy)
        unlock(&work.wbufSpans.lock)
}

// freeSomeWbufs frees some workbufs back to the heap and returns
// true if it should be called again to free more.
func freeSomeWbufs(preemptible bool) bool {
        const batchSize = 64 // ~1–2 µs per span.
        lock(&work.wbufSpans.lock)
        if gcphase != _GCoff || work.wbufSpans.free.isEmpty() {
                unlock(&work.wbufSpans.lock)
                return false
        }
        systemstack(func() {
                gp := getg().m.curg
                for i := 0; i < batchSize && !(preemptible && gp.preempt); i++ {
                        span := work.wbufSpans.free.first
                        if span == nil {
                                break
                        }
                        work.wbufSpans.free.remove(span)
                        mheap_.freeManual(span, &memstats.gc_sys)
                }
        })
        more := !work.wbufSpans.free.isEmpty()
        unlock(&work.wbufSpans.lock)
        return more
}