[dev.garbage] all: merge dev.cc into dev.garbage

[gostls13.git] / src / runtime / mgc.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.

// TODO(rsc): The code having to do with the heap bitmap needs very serious cleanup.
// It has gotten completely out of control.

// Garbage collector (GC).
//
// The GC runs concurrently with mutator threads, is type accurate (aka precise), allows multiple GC
// thread to run in parallel. It is a concurrent mark and sweep that uses a write barrier. It is
// non-generational and non-compacting. Allocation is done using size segregated per P allocation
// areas to minimize fragmentation while eliminating locks in the common case.
//
// The algorithm decomposes into several steps.
// This is a high level description of the algorithm being used. For an overview of GC a good
// place to start is Richard Jones' gchandbook.org.
//
// The algorithm's intellectual heritage includes Dijkstra's on-the-fly algorithm, see
// Edsger W. Dijkstra, Leslie Lamport, A. J. Martin, C. S. Scholten, and E. F. M. Steffens. 1978.
// On-the-fly garbage collection: an exercise in cooperation. Commun. ACM 21, 11 (November 1978), 966-975.
// For journal quality proofs that these steps are complete, correct, and terminate see
// Hudson, R., and Moss, J.E.B. Copying Garbage Collection without stopping the world.
// Concurrency and Computation: Practice and Experience 15(3-5), 2003.
//
//  0. Set phase = GCscan from GCoff.
//  1. Wait for all P's to acknowledge phase change.
//         At this point all goroutines have passed through a GC safepoint and
//         know we are in the GCscan phase.
//  2. GC scans all goroutine stacks, mark and enqueues all encountered pointers
//       (marking avoids most duplicate enqueuing but races may produce duplication which is benign).
//       Preempted goroutines are scanned before P schedules next goroutine.
//  3. Set phase = GCmark.
//  4. Wait for all P's to acknowledge phase change.
//  5. Now write barrier marks and enqueues black, grey, or white to white pointers.
//       Malloc still allocates white (non-marked) objects.
//  6. Meanwhile GC transitively walks the heap marking reachable objects.
//  7. When GC finishes marking heap, it preempts P's one-by-one and
//       retakes partial wbufs (filled by write barrier or during a stack scan of the goroutine
//       currently scheduled on the P).
//  8. Once the GC has exhausted all available marking work it sets phase = marktermination.
//  9. Wait for all P's to acknowledge phase change.
// 10. Malloc now allocates black objects, so number of unmarked reachable objects
//        monotonically decreases.
// 11. GC preempts P's one-by-one taking partial wbufs and marks all unmarked yet reachable objects.
// 12. When GC completes a full cycle over P's and discovers no new grey
//         objects, (which means all reachable objects are marked) set phase = GCsweep.
// 13. Wait for all P's to acknowledge phase change.
// 14. Now malloc allocates white (but sweeps spans before use).
//         Write barrier becomes nop.
// 15. GC does background sweeping, see description below.
// 16. When sweeping is complete set phase to GCoff.
// 17. When sufficient allocation has taken place replay the sequence starting at 0 above,
//         see discussion of GC rate below.

// Changing phases.
// Phases are changed by setting the gcphase to the next phase and possibly calling ackgcphase.
// All phase action must be benign in the presence of a change.
// Starting with GCoff
// GCoff to GCscan
//     GSscan scans stacks and globals greying them and never marks an object black.
//     Once all the P's are aware of the new phase they will scan gs on preemption.
//     This means that the scanning of preempted gs can't start until all the Ps
//     have acknowledged.
// GCscan to GCmark
//     GCMark turns on the write barrier which also only greys objects. No scanning
//     of objects (making them black) can happen until all the Ps have acknowledged
//     the phase change.
// GCmark to GCmarktermination
//     The only change here is that we start allocating black so the Ps must acknowledge
//     the change before we begin the termination algorithm
// GCmarktermination to GSsweep
//     Object currently on the freelist must be marked black for this to work.
//     Are things on the free lists black or white? How does the sweep phase work?

// Concurrent sweep.
// The sweep phase proceeds concurrently with normal program execution.
// The heap is swept span-by-span both lazily (when a goroutine needs another span)
// and concurrently in a background goroutine (this helps programs that are not CPU bound).
// However, at the end of the stop-the-world GC phase we don't know the size of the live heap,
// and so next_gc calculation is tricky and happens as follows.
// At the end of the stop-the-world phase next_gc is conservatively set based on total
// heap size; all spans are marked as "needs sweeping".
// Whenever a span is swept, next_gc is decremented by GOGC*newly_freed_memory.
// The background sweeper goroutine simply sweeps spans one-by-one bringing next_gc
// closer to the target value. However, this is not enough to avoid over-allocating memory.
// Consider that a goroutine wants to allocate a new span for a large object and
// there are no free swept spans, but there are small-object unswept spans.
// If the goroutine naively allocates a new span, it can surpass the yet-unknown
// target next_gc value. In order to prevent such cases (1) when a goroutine needs
// to allocate a new small-object span, it sweeps small-object spans for the same
// object size until it frees at least one object; (2) when a goroutine needs to
// allocate large-object span from heap, it sweeps spans until it frees at least
// that many pages into heap. Together these two measures ensure that we don't surpass
// target next_gc value by a large margin. There is an exception: if a goroutine sweeps
// and frees two nonadjacent one-page spans to the heap, it will allocate a new two-page span,
// but there can still be other one-page unswept spans which could be combined into a two-page span.
// It's critical to ensure that no operations proceed on unswept spans (that would corrupt
// mark bits in GC bitmap). During GC all mcaches are flushed into the central cache,
// so they are empty. When a goroutine grabs a new span into mcache, it sweeps it.
// When a goroutine explicitly frees an object or sets a finalizer, it ensures that
// the span is swept (either by sweeping it, or by waiting for the concurrent sweep to finish).
// The finalizer goroutine is kicked off only when all spans are swept.
// When the next GC starts, it sweeps all not-yet-swept spans (if any).

// GC rate.
// Next GC is after we've allocated an extra amount of memory proportional to
// the amount already in use. The proportion is controlled by GOGC environment variable
// (100 by default). If GOGC=100 and we're using 4M, we'll GC again when we get to 8M
// (this mark is tracked in next_gc variable). This keeps the GC cost in linear
// proportion to the allocation cost. Adjusting GOGC just changes the linear constant
// (and also the amount of extra memory used).

package runtime

import "unsafe"

const (
        _DebugGC         = 0
        _DebugGCPtrs     = false // if true, print trace of every pointer load during GC
        _ConcurrentSweep = true

        _WorkbufSize     = 4 * 1024
        _FinBlockSize    = 4 * 1024
        _RootData        = 0
        _RootBss         = 1
        _RootFinalizers  = 2
        _RootSpans       = 3
        _RootFlushCaches = 4
        _RootCount       = 5
)

// ptrmask for an allocation containing a single pointer.
var oneptr = [...]uint8{bitsPointer}

// Initialized from $GOGC.  GOGC=off means no GC.
var gcpercent int32

// Holding worldsema grants an M the right to try to stop the world.
// The procedure is:
//
//      semacquire(&worldsema);
//      m.gcing = 1;
//      stoptheworld();
//
//      ... do stuff ...
//
//      m.gcing = 0;
//      semrelease(&worldsema);
//      starttheworld();
//
var worldsema uint32 = 1

// It is a bug if bits does not have bitBoundary set but
// there are still some cases where this happens related
// to stack spans.
type markbits struct {
        bitp  *byte   // pointer to the byte holding xbits
        shift uintptr // bits xbits needs to be shifted to get bits
        xbits byte    // byte holding all the bits from *bitp
        bits  byte    // mark and boundary bits relevant to corresponding slot.
        tbits byte    // pointer||scalar bits relevant to corresponding slot.
}

type workbuf struct {
        node lfnode // must be first
        nobj uintptr
        obj  [(_WorkbufSize - unsafe.Sizeof(lfnode{}) - ptrSize) / ptrSize]uintptr
}

var data, edata, bss, ebss, gcdata, gcbss struct{}

var finlock mutex  // protects the following variables
var fing *g        // goroutine that runs finalizers
var finq *finblock // list of finalizers that are to be executed
var finc *finblock // cache of free blocks
var finptrmask [_FinBlockSize / ptrSize / pointersPerByte]byte
var fingwait bool
var fingwake bool
var allfin *finblock // list of all blocks

var gcdatamask bitvector
var gcbssmask bitvector

var gclock mutex

var badblock [1024]uintptr
var nbadblock int32

type workdata struct {
        full    uint64                // lock-free list of full blocks
        empty   uint64                // lock-free list of empty blocks
        partial uint64                // lock-free list of partially filled blocks
        pad0    [_CacheLineSize]uint8 // prevents false-sharing between full/empty and nproc/nwait
        nproc   uint32
        tstart  int64
        nwait   uint32
        ndone   uint32
        alldone note
        markfor *parfor

        // Copy of mheap.allspans for marker or sweeper.
        spans []*mspan
}

var work workdata

//go:linkname weak_cgo_allocate go.weak.runtime._cgo_allocate_internal
var weak_cgo_allocate byte

// Is _cgo_allocate linked into the binary?
func have_cgo_allocate() bool {
        return &weak_cgo_allocate != nil
}

// To help debug the concurrent GC we remark with the world
// stopped ensuring that any object encountered has their normal
// mark bit set. To do this we use an orthogonal bit
// pattern to indicate the object is marked. The following pattern
// uses the upper two bits in the object's bounday nibble.
// 01: scalar  not marked
// 10: pointer not marked
// 11: pointer     marked
// 00: scalar      marked
// Xoring with 01 will flip the pattern from marked to unmarked and vica versa.
// The higher bit is 1 for pointers and 0 for scalars, whether the object
// is marked or not.
// The first nibble no longer holds the bitsDead pattern indicating that the
// there are no more pointers in the object. This information is held
// in the second nibble.

// When marking an object if the bool checkmark is true one uses the above
// encoding, otherwise one uses the bitMarked bit in the lower two bits
// of the nibble.
var (
        checkmark         = false
        gccheckmarkenable = true
)

// Is address b in the known heap. If it doesn't have a valid gcmap
// returns false. For example pointers into stacks will return false.
func inheap(b uintptr) bool {
        if b == 0 || b < mheap_.arena_start || b >= mheap_.arena_used {
                return false
        }
        // Not a beginning of a block, consult span table to find the block beginning.
        k := b >> _PageShift
        x := k
        x -= mheap_.arena_start >> _PageShift
        s := h_spans[x]
        if s == nil || pageID(k) < s.start || b >= s.limit || s.state != mSpanInUse {
                return false
        }
        return true
}

// Given an address in the heap return the relevant byte from the gcmap. This routine
// can be used on addresses to the start of an object or to the interior of the an object.
func slottombits(obj uintptr, mbits *markbits) {
        off := (obj&^(ptrSize-1) - mheap_.arena_start) / ptrSize
        mbits.bitp = (*byte)(unsafe.Pointer(mheap_.arena_start - off/wordsPerBitmapByte - 1))
        mbits.shift = off % wordsPerBitmapByte * gcBits
        mbits.xbits = *mbits.bitp
        mbits.bits = (mbits.xbits >> mbits.shift) & bitMask
        mbits.tbits = ((mbits.xbits >> mbits.shift) & bitPtrMask) >> 2
}

// b is a pointer into the heap.
// Find the start of the object refered to by b.
// Set mbits to the associated bits from the bit map.
// If b is not a valid heap object return nil and
// undefined values in mbits.
func objectstart(b uintptr, mbits *markbits) uintptr {
        obj := b &^ (ptrSize - 1)
        for {
                slottombits(obj, mbits)
                if mbits.bits&bitBoundary == bitBoundary {
                        break
                }

                // Not a beginning of a block, consult span table to find the block beginning.
                k := b >> _PageShift
                x := k
                x -= mheap_.arena_start >> _PageShift
                s := h_spans[x]
                if s == nil || pageID(k) < s.start || b >= s.limit || s.state != mSpanInUse {
                        if s != nil && s.state == _MSpanStack {
                                return 0 // This is legit.
                        }

                        // The following ensures that we are rigorous about what data
                        // structures hold valid pointers
                        if false {
                                // Still happens sometimes. We don't know why.
                                printlock()
                                print("runtime:objectstart Span weird: obj=", hex(obj), " k=", hex(k))
                                if s == nil {
                                        print(" s=nil\n")
                                } else {
                                        print(" s.start=", hex(s.start<<_PageShift), " s.limit=", hex(s.limit), " s.state=", s.state, "\n")
                                }
                                printunlock()
                                gothrow("objectstart: bad pointer in unexpected span")
                        }
                        return 0
                }

                p := uintptr(s.start) << _PageShift
                if s.sizeclass != 0 {
                        size := s.elemsize
                        idx := (obj - p) / size
                        p = p + idx*size
                }
                if p == obj {
                        print("runtime: failed to find block beginning for ", hex(p), " s=", hex(s.start*_PageSize), " s.limit=", s.limit, "\n")
                        gothrow("failed to find block beginning")
                }
                obj = p
        }

        // if size(obj.firstfield) < PtrSize, the &obj.secondfield could map to the boundary bit
        // Clear any low bits to get to the start of the object.
        // greyobject depends on this.
        return obj
}

// Slow for now as we serialize this, since this is on a debug path
// speed is not critical at this point.
var andlock mutex

func atomicand8(src *byte, val byte) {
        lock(&andlock)
        *src &= val
        unlock(&andlock)
}

// Mark using the checkmark scheme.
func docheckmark(mbits *markbits) {
        // xor 01 moves 01(scalar unmarked) to 00(scalar marked)
        // and 10(pointer unmarked) to 11(pointer marked)
        if mbits.tbits == _BitsScalar {
                atomicand8(mbits.bitp, ^byte(_BitsCheckMarkXor<<mbits.shift<<2))
        } else if mbits.tbits == _BitsPointer {
                atomicor8(mbits.bitp, byte(_BitsCheckMarkXor<<mbits.shift<<2))
        }

        // reload bits for ischeckmarked
        mbits.xbits = *mbits.bitp
        mbits.bits = (mbits.xbits >> mbits.shift) & bitMask
        mbits.tbits = ((mbits.xbits >> mbits.shift) & bitPtrMask) >> 2
}

// In the default scheme does mbits refer to a marked object.
func ismarked(mbits *markbits) bool {
        if mbits.bits&bitBoundary != bitBoundary {
                gothrow("ismarked: bits should have boundary bit set")
        }
        return mbits.bits&bitMarked == bitMarked
}

// In the checkmark scheme does mbits refer to a marked object.
func ischeckmarked(mbits *markbits) bool {
        if mbits.bits&bitBoundary != bitBoundary {
                gothrow("ischeckmarked: bits should have boundary bit set")
        }
        return mbits.tbits == _BitsScalarMarked || mbits.tbits == _BitsPointerMarked
}

// When in GCmarkterminate phase we allocate black.
func gcmarknewobject_m(obj uintptr) {
        if gcphase != _GCmarktermination {
                gothrow("marking new object while not in mark termination phase")
        }
        if checkmark { // The world should be stopped so this should not happen.
                gothrow("gcmarknewobject called while doing checkmark")
        }

        var mbits markbits
        slottombits(obj, &mbits)
        if mbits.bits&bitMarked != 0 {
                return
        }

        // Each byte of GC bitmap holds info for two words.
        // If the current object is larger than two words, or if the object is one word
        // but the object it shares the byte with is already marked,
        // then all the possible concurrent updates are trying to set the same bit,
        // so we can use a non-atomic update.
        if mbits.xbits&(bitMask|(bitMask<<gcBits)) != bitBoundary|bitBoundary<<gcBits || work.nproc == 1 {
                *mbits.bitp = mbits.xbits | bitMarked<<mbits.shift
        } else {
                atomicor8(mbits.bitp, bitMarked<<mbits.shift)
        }
}

// obj is the start of an object with mark mbits.
// If it isn't already marked, mark it and enqueue into workbuf.
// Return possibly new workbuf to use.
func greyobject(obj uintptr, mbits *markbits, wbuf *workbuf) *workbuf {
        // obj should be start of allocation, and so must be at least pointer-aligned.
        if obj&(ptrSize-1) != 0 {
                gothrow("greyobject: obj not pointer-aligned")
        }

        if checkmark {
                if !ismarked(mbits) {
                        print("runtime:greyobject: checkmarks finds unexpected unmarked object obj=", hex(obj), ", mbits->bits=", hex(mbits.bits), " *mbits->bitp=", hex(*mbits.bitp), "\n")

                        k := obj >> _PageShift
                        x := k
                        x -= mheap_.arena_start >> _PageShift
                        s := h_spans[x]
                        printlock()
                        print("runtime:greyobject Span: obj=", hex(obj), " k=", hex(k))
                        if s == nil {
                                print(" s=nil\n")
                        } else {
                                print(" s.start=", hex(s.start*_PageSize), " s.limit=", hex(s.limit), " s.sizeclass=", s.sizeclass, " s.elemsize=", s.elemsize, "\n")
                                // NOTE(rsc): This code is using s.sizeclass as an approximation of the
                                // number of pointer-sized words in an object. Perhaps not what was intended.
                                for i := 0; i < int(s.sizeclass); i++ {
                                        print(" *(obj+", i*ptrSize, ") = ", hex(*(*uintptr)(unsafe.Pointer(obj + uintptr(i)*ptrSize))), "\n")
                                }
                        }
                        gothrow("checkmark found unmarked object")
                }
                if ischeckmarked(mbits) {
                        return wbuf
                }
                docheckmark(mbits)
                if !ischeckmarked(mbits) {
                        print("mbits xbits=", hex(mbits.xbits), " bits=", hex(mbits.bits), " tbits=", hex(mbits.tbits), " shift=", mbits.shift, "\n")
                        gothrow("docheckmark and ischeckmarked disagree")
                }
        } else {
                // If marked we have nothing to do.
                if mbits.bits&bitMarked != 0 {
                        return wbuf
                }

                // Each byte of GC bitmap holds info for two words.
                // If the current object is larger than two words, or if the object is one word
                // but the object it shares the byte with is already marked,
                // then all the possible concurrent updates are trying to set the same bit,
                // so we can use a non-atomic update.
                if mbits.xbits&(bitMask|bitMask<<gcBits) != bitBoundary|bitBoundary<<gcBits || work.nproc == 1 {
                        *mbits.bitp = mbits.xbits | bitMarked<<mbits.shift
                } else {
                        atomicor8(mbits.bitp, bitMarked<<mbits.shift)
                }
        }

        if !checkmark && (mbits.xbits>>(mbits.shift+2))&_BitsMask == _BitsDead {
                return wbuf // noscan object
        }

        // Queue the obj for scanning. The PREFETCH(obj) logic has been removed but
        // seems like a nice optimization that can be added back in.
        // There needs to be time between the PREFETCH and the use.
        // Previously we put the obj in an 8 element buffer that is drained at a rate
        // to give the PREFETCH time to do its work.
        // Use of PREFETCHNTA might be more appropriate than PREFETCH

        // If workbuf is full, obtain an empty one.
        if wbuf.nobj >= uintptr(len(wbuf.obj)) {
                wbuf = getempty(wbuf)
        }

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

// Scan the object b of size n, adding pointers to wbuf.
// Return possibly new wbuf to use.
// If ptrmask != nil, it specifies where pointers are in b.
// If ptrmask == nil, the GC bitmap should be consulted.
// In this case, n may be an overestimate of the size; the GC bitmap
// must also be used to make sure the scan stops at the end of b.
func scanobject(b, n uintptr, ptrmask *uint8, wbuf *workbuf) *workbuf {
        arena_start := mheap_.arena_start
        arena_used := mheap_.arena_used

        // Find bits of the beginning of the object.
        var ptrbitp unsafe.Pointer
        var mbits markbits
        if ptrmask == nil {
                b = objectstart(b, &mbits)
                if b == 0 {
                        return wbuf
                }
                ptrbitp = unsafe.Pointer(mbits.bitp)
        }
        for i := uintptr(0); i < n; i += ptrSize {
                // Find bits for this word.
                var bits uintptr
                if ptrmask != nil {
                        // dense mask (stack or data)
                        bits = (uintptr(*(*byte)(add(unsafe.Pointer(ptrmask), (i/ptrSize)/4))) >> (((i / ptrSize) % 4) * bitsPerPointer)) & bitsMask
                } else {
                        // Check if we have reached end of span.
                        // n is an overestimate of the size of the object.
                        if (b+i)%_PageSize == 0 && h_spans[(b-arena_start)>>_PageShift] != h_spans[(b+i-arena_start)>>_PageShift] {
                                break
                        }

                        // Consult GC bitmap.
                        bits = uintptr(*(*byte)(ptrbitp))
                        if wordsPerBitmapByte != 2 {
                                gothrow("alg doesn't work for wordsPerBitmapByte != 2")
                        }
                        j := (uintptr(b) + i) / ptrSize & 1 // j indicates upper nibble or lower nibble
                        bits >>= gcBits * j
                        if i == 0 {
                                bits &^= bitBoundary
                        }
                        ptrbitp = add(ptrbitp, -j)

                        if bits&bitBoundary != 0 && i != 0 {
                                break // reached beginning of the next object
                        }
                        bits = (bits & bitPtrMask) >> 2 // bits refer to the type bits.

                        if i != 0 && bits == bitsDead { // BitsDead in first nibble not valid during checkmark
                                break // reached no-scan part of the object
                        }
                }

                if bits <= _BitsScalar { // _BitsScalar, _BitsDead, _BitsScalarMarked
                        continue
                }

                if bits&_BitsPointer != _BitsPointer {
                        print("gc checkmark=", checkmark, " b=", hex(b), " ptrmask=", ptrmask, " mbits.bitp=", mbits.bitp, " mbits.xbits=", hex(mbits.xbits), " bits=", hex(bits), "\n")
                        gothrow("unexpected garbage collection bits")
                }

                obj := *(*uintptr)(unsafe.Pointer(b + i))

                // At this point we have extracted the next potential pointer.
                // Check if it points into heap.
                if obj == 0 || obj < arena_start || obj >= arena_used {
                        continue
                }

                // Mark the object. return some important bits.
                // We we combine the following two rotines we don't have to pass mbits or obj around.
                var mbits markbits
                obj = objectstart(obj, &mbits)
                if obj == 0 {
                        continue
                }
                wbuf = greyobject(obj, &mbits, wbuf)
        }
        return wbuf
}

// scanblock starts by scanning b as scanobject would.
// If the gcphase is GCscan, that's all scanblock does.
// Otherwise it traverses some fraction of the pointers it found in b, recursively.
// As a special case, scanblock(nil, 0, nil) means to scan previously queued work,
// stopping only when no work is left in the system.
func scanblock(b, n uintptr, ptrmask *uint8) {
        wbuf := getpartialorempty()
        if b != 0 {
                wbuf = scanobject(b, n, ptrmask, wbuf)
                if gcphase == _GCscan {
                        if inheap(b) && ptrmask == nil {
                                // b is in heap, we are in GCscan so there should be a ptrmask.
                                gothrow("scanblock: In GCscan phase and inheap is true.")
                        }
                        // GCscan only goes one level deep since mark wb not turned on.
                        putpartial(wbuf)
                        return
                }
        }
        if gcphase == _GCscan {
                gothrow("scanblock: In GCscan phase but no b passed in.")
        }

        keepworking := b == 0

        // ptrmask can have 2 possible values:
        // 1. nil - obtain pointer mask from GC bitmap.
        // 2. pointer to a compact mask (for stacks and data).
        for {
                if wbuf.nobj == 0 {
                        if !keepworking {
                                putempty(wbuf)
                                return
                        }
                        // Refill workbuf from global queue.
                        wbuf = getfull(wbuf)
                        if wbuf == nil { // nil means out of work barrier reached
                                return
                        }

                        if wbuf.nobj <= 0 {
                                gothrow("runtime:scanblock getfull returns empty buffer")
                        }
                }

                // If another proc wants a pointer, give it some.
                if work.nwait > 0 && wbuf.nobj > 4 && work.full == 0 {
                        wbuf = handoff(wbuf)
                }

                // This might be a good place to add prefetch code...
                // if(wbuf->nobj > 4) {
                //         PREFETCH(wbuf->obj[wbuf->nobj - 3];
                //  }
                wbuf.nobj--
                b = wbuf.obj[wbuf.nobj]
                wbuf = scanobject(b, mheap_.arena_used-b, nil, wbuf)
        }
}

func markroot(desc *parfor, i uint32) {
        // Note: if you add a case here, please also update heapdump.c:dumproots.
        switch i {
        case _RootData:
                scanblock(uintptr(unsafe.Pointer(&data)), uintptr(unsafe.Pointer(&edata))-uintptr(unsafe.Pointer(&data)), gcdatamask.bytedata)

        case _RootBss:
                scanblock(uintptr(unsafe.Pointer(&bss)), uintptr(unsafe.Pointer(&ebss))-uintptr(unsafe.Pointer(&bss)), gcbssmask.bytedata)

        case _RootFinalizers:
                for fb := allfin; fb != nil; fb = fb.alllink {
                        scanblock(uintptr(unsafe.Pointer(&fb.fin[0])), uintptr(fb.cnt)*unsafe.Sizeof(fb.fin[0]), &finptrmask[0])
                }

        case _RootSpans:
                // mark MSpan.specials
                sg := mheap_.sweepgen
                for spanidx := uint32(0); spanidx < uint32(len(work.spans)); spanidx++ {
                        s := work.spans[spanidx]
                        if s.state != mSpanInUse {
                                continue
                        }
                        if !checkmark && s.sweepgen != sg {
                                // sweepgen was updated (+2) during non-checkmark GC pass
                                print("sweep ", s.sweepgen, " ", sg, "\n")
                                gothrow("gc: unswept span")
                        }
                        for sp := s.specials; sp != nil; sp = sp.next {
                                if sp.kind != _KindSpecialFinalizer {
                                        continue
                                }
                                // don't mark finalized object, but scan it so we
                                // retain everything it points to.
                                spf := (*specialfinalizer)(unsafe.Pointer(sp))
                                // A finalizer can be set for an inner byte of an object, find object beginning.
                                p := uintptr(s.start<<_PageShift) + uintptr(spf.special.offset)/s.elemsize*s.elemsize
                                if gcphase != _GCscan {
                                        scanblock(p, s.elemsize, nil) // scanned during mark phase
                                }
                                scanblock(uintptr(unsafe.Pointer(&spf.fn)), ptrSize, &oneptr[0])
                        }
                }

        case _RootFlushCaches:
                if gcphase != _GCscan { // Do not flush mcaches during GCscan phase.
                        flushallmcaches()
                }

        default:
                // the rest is scanning goroutine stacks
                if uintptr(i-_RootCount) >= allglen {
                        gothrow("markroot: bad index")
                }
                gp := allgs[i-_RootCount]

                // remember when we've first observed the G blocked
                // needed only to output in traceback
                status := readgstatus(gp) // We are not in a scan state
                if (status == _Gwaiting || status == _Gsyscall) && gp.waitsince == 0 {
                        gp.waitsince = work.tstart
                }

                // Shrink a stack if not much of it is being used but not in the scan phase.
                if gcphase != _GCscan { // Do not shrink during GCscan phase.
                        shrinkstack(gp)
                }
                if readgstatus(gp) == _Gdead {
                        gp.gcworkdone = true
                } else {
                        gp.gcworkdone = false
                }
                restart := stopg(gp)

                // goroutine will scan its own stack when it stops running.
                // Wait until it has.
                for readgstatus(gp) == _Grunning && !gp.gcworkdone {
                }

                // scanstack(gp) is done as part of gcphasework
                // But to make sure we finished we need to make sure that
                // the stack traps have all responded so drop into
                // this while loop until they respond.
                for !gp.gcworkdone {
                        status = readgstatus(gp)
                        if status == _Gdead {
                                gp.gcworkdone = true // scan is a noop
                                break
                        }
                        if status == _Gwaiting || status == _Grunnable {
                                restart = stopg(gp)
                        }
                }
                if restart {
                        restartg(gp)
                }
        }
}

// Get an empty work buffer off the work.empty list,
// allocating new buffers as needed.
func getempty(b *workbuf) *workbuf {
        if b != nil {
                putfull(b)
                b = nil
        }
        if work.empty != 0 {
                b = (*workbuf)(lfstackpop(&work.empty))
        }
        if b != nil && b.nobj != 0 {
                _g_ := getg()
                print("m", _g_.m.id, ": getempty: popped b=", b, " with non-zero b.nobj=", b.nobj, "\n")
                gothrow("getempty: workbuffer not empty, b->nobj not 0")
        }
        if b == nil {
                b = (*workbuf)(persistentalloc(unsafe.Sizeof(*b), _CacheLineSize, &memstats.gc_sys))
                b.nobj = 0
        }
        return b
}

func putempty(b *workbuf) {
        if b.nobj != 0 {
                gothrow("putempty: b->nobj not 0")
        }
        lfstackpush(&work.empty, &b.node)
}

func putfull(b *workbuf) {
        if b.nobj <= 0 {
                gothrow("putfull: b->nobj <= 0")
        }
        lfstackpush(&work.full, &b.node)
}

// Get an partially empty work buffer
// if none are available get an empty one.
func getpartialorempty() *workbuf {
        b := (*workbuf)(lfstackpop(&work.partial))
        if b == nil {
                b = getempty(nil)
        }
        return b
}

func putpartial(b *workbuf) {
        if b.nobj == 0 {
                lfstackpush(&work.empty, &b.node)
        } else if b.nobj < uintptr(len(b.obj)) {
                lfstackpush(&work.partial, &b.node)
        } else if b.nobj == uintptr(len(b.obj)) {
                lfstackpush(&work.full, &b.node)
        } else {
                print("b=", b, " b.nobj=", b.nobj, " len(b.obj)=", len(b.obj), "\n")
                gothrow("putpartial: bad Workbuf b.nobj")
        }
}

// Get a full work buffer off the work.full or a partially
// filled one off the work.partial 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.
func getfull(b *workbuf) *workbuf {
        if b != nil {
                putempty(b)
        }

        b = (*workbuf)(lfstackpop(&work.full))
        if b == nil {
                b = (*workbuf)(lfstackpop(&work.partial))
        }
        if b != nil || work.nproc == 1 {
                return b
        }

        xadd(&work.nwait, +1)
        for i := 0; ; i++ {
                if work.full != 0 {
                        xadd(&work.nwait, -1)
                        b = (*workbuf)(lfstackpop(&work.full))
                        if b == nil {
                                b = (*workbuf)(lfstackpop(&work.partial))
                        }
                        if b != nil {
                                return b
                        }
                        xadd(&work.nwait, +1)
                }
                if work.nwait == work.nproc {
                        return nil
                }
                _g_ := getg()
                if i < 10 {
                        _g_.m.gcstats.nprocyield++
                        procyield(20)
                } else if i < 20 {
                        _g_.m.gcstats.nosyield++
                        osyield()
                } else {
                        _g_.m.gcstats.nsleep++
                        usleep(100)
                }
        }
}

func handoff(b *workbuf) *workbuf {
        // Make new buffer with half of b's pointers.
        b1 := getempty(nil)
        n := b.nobj / 2
        b.nobj -= n
        b1.nobj = n
        memmove(unsafe.Pointer(&b1.obj[0]), unsafe.Pointer(&b.obj[b.nobj]), n*unsafe.Sizeof(b1.obj[0]))
        _g_ := getg()
        _g_.m.gcstats.nhandoff++
        _g_.m.gcstats.nhandoffcnt += uint64(n)

        // Put b on full list - let first half of b get stolen.
        lfstackpush(&work.full, &b.node)
        return b1
}

func stackmapdata(stkmap *stackmap, n int32) bitvector {
        if n < 0 || n >= stkmap.n {
                gothrow("stackmapdata: index out of range")
        }
        return bitvector{stkmap.nbit, (*byte)(add(unsafe.Pointer(&stkmap.bytedata), uintptr(n*((stkmap.nbit+31)/32*4))))}
}

// Scan a stack frame: local variables and function arguments/results.
func scanframe(frame *stkframe, unused unsafe.Pointer) bool {

        f := frame.fn
        targetpc := frame.continpc
        if targetpc == 0 {
                // Frame is dead.
                return true
        }
        if _DebugGC > 1 {
                print("scanframe ", gofuncname(f), "\n")
        }
        if targetpc != f.entry {
                targetpc--
        }
        pcdata := pcdatavalue(f, _PCDATA_StackMapIndex, targetpc)
        if pcdata == -1 {
                // We do not have a valid pcdata value but there might be a
                // stackmap for this function.  It is likely that we are looking
                // at the function prologue, assume so and hope for the best.
                pcdata = 0
        }

        // Scan local variables if stack frame has been allocated.
        size := frame.varp - frame.sp
        var minsize uintptr
        if thechar != '6' && thechar != '8' {
                minsize = ptrSize
        } else {
                minsize = 0
        }
        if size > minsize {
                stkmap := (*stackmap)(funcdata(f, _FUNCDATA_LocalsPointerMaps))
                if stkmap == nil || stkmap.n <= 0 {
                        print("runtime: frame ", gofuncname(f), " untyped locals ", hex(frame.varp-size), "+", hex(size), "\n")
                        gothrow("missing stackmap")
                }

                // Locals bitmap information, scan just the pointers in locals.
                if pcdata < 0 || pcdata >= stkmap.n {
                        // don't know where we are
                        print("runtime: pcdata is ", pcdata, " and ", stkmap.n, " locals stack map entries for ", gofuncname(f), " (targetpc=", targetpc, ")\n")
                        gothrow("scanframe: bad symbol table")
                }
                bv := stackmapdata(stkmap, pcdata)
                size = (uintptr(bv.n) * ptrSize) / bitsPerPointer
                scanblock(frame.varp-size, uintptr(bv.n)/bitsPerPointer*ptrSize, bv.bytedata)
        }

        // Scan arguments.
        if frame.arglen > 0 {
                var bv bitvector
                if frame.argmap != nil {
                        bv = *frame.argmap
                } else {
                        stkmap := (*stackmap)(funcdata(f, _FUNCDATA_ArgsPointerMaps))
                        if stkmap == nil || stkmap.n <= 0 {
                                print("runtime: frame ", gofuncname(f), " untyped args ", hex(frame.argp), "+", hex(frame.arglen), "\n")
                                gothrow("missing stackmap")
                        }
                        if pcdata < 0 || pcdata >= stkmap.n {
                                // don't know where we are
                                print("runtime: pcdata is ", pcdata, " and ", stkmap.n, " args stack map entries for ", gofuncname(f), " (targetpc=", targetpc, ")\n")
                                gothrow("scanframe: bad symbol table")
                        }
                        bv = stackmapdata(stkmap, pcdata)
                }
                scanblock(frame.argp, uintptr(bv.n)/bitsPerPointer*ptrSize, bv.bytedata)
        }
        return true
}

func scanstack(gp *g) {
        // TODO(rsc): Due to a precedence error, this was never checked in the original C version.
        // If you enable the check, the gothrow happens.
        /*
                if readgstatus(gp)&_Gscan == 0 {
                        print("runtime: gp=", gp, ", goid=", gp.goid, ", gp->atomicstatus=", readgstatus(gp), "\n")
                        gothrow("mark - bad status")
                }
        */

        switch readgstatus(gp) &^ _Gscan {
        default:
                print("runtime: gp=", gp, ", goid=", gp.goid, ", gp->atomicstatus=", readgstatus(gp), "\n")
                gothrow("mark - bad status")
        case _Gdead:
                return
        case _Grunning:
                print("runtime: gp=", gp, ", goid=", gp.goid, ", gp->atomicstatus=", readgstatus(gp), "\n")
                gothrow("scanstack: goroutine not stopped")
        case _Grunnable, _Gsyscall, _Gwaiting:
                // ok
        }

        if gp == getg() {
                gothrow("can't scan our own stack")
        }
        mp := gp.m
        if mp != nil && mp.helpgc != 0 {
                gothrow("can't scan gchelper stack")
        }

        gentraceback(^uintptr(0), ^uintptr(0), 0, gp, 0, nil, 0x7fffffff, scanframe, nil, 0)
        tracebackdefers(gp, scanframe, nil)
}

// If the slot is grey or black return true, if white return false.
// If the slot is not in the known heap and thus does not have a valid GC bitmap then
// it is considered grey. Globals and stacks can hold such slots.
// The slot is grey if its mark bit is set and it is enqueued to be scanned.
// The slot is black if it has already been scanned.
// It is white if it has a valid mark bit and the bit is not set.
func shaded(slot uintptr) bool {
        if !inheap(slot) { // non-heap slots considered grey
                return true
        }

        var mbits markbits
        valid := objectstart(slot, &mbits)
        if valid == 0 {
                return true
        }

        if checkmark {
                return ischeckmarked(&mbits)
        }

        return mbits.bits&bitMarked != 0
}

// Shade the object if it isn't already.
// The object is not nil and known to be in the heap.
func shade(b uintptr) {
        if !inheap(b) {
                gothrow("shade: passed an address not in the heap")
        }

        wbuf := getpartialorempty()
        // Mark the object, return some important bits.
        // If we combine the following two rotines we don't have to pass mbits or obj around.
        var mbits markbits
        obj := objectstart(b, &mbits)
        if obj != 0 {
                wbuf = greyobject(obj, &mbits, wbuf) // augments the wbuf
        }
        putpartial(wbuf)
}

// This is the Dijkstra barrier coarsened to always shade the ptr (dst) object.
// The original Dijkstra barrier only shaded ptrs being placed in black slots.
//
// Shade indicates that it has seen a white pointer by adding the referent
// to wbuf as well as marking it.
//
// slot is the destination (dst) in go code
// ptr is the value that goes into the slot (src) in the go code
//
// Dijkstra pointed out that maintaining the no black to white
// pointers means that white to white pointers not need
// to be noted by the write barrier. Furthermore if either
// white object dies before it is reached by the
// GC then the object can be collected during this GC cycle
// instead of waiting for the next cycle. Unfortunately the cost of
// ensure that the object holding the slot doesn't concurrently
// change to black without the mutator noticing seems prohibitive.
//
// Consider the following example where the mutator writes into
// a slot and then loads the slot's mark bit while the GC thread
// writes to the slot's mark bit and then as part of scanning reads
// the slot.
//
// Initially both [slot] and [slotmark] are 0 (nil)
// Mutator thread          GC thread
// st [slot], ptr          st [slotmark], 1
//
// ld r1, [slotmark]       ld r2, [slot]
//
// This is a classic example of independent reads of independent writes,
// aka IRIW. The question is if r1==r2==0 is allowed and for most HW the
// answer is yes without inserting a memory barriers between the st and the ld.
// These barriers are expensive so we have decided that we will
// always grey the ptr object regardless of the slot's color.
func gcmarkwb_m(slot *uintptr, ptr uintptr) {
        switch gcphase {
        default:
                gothrow("gcphasework in bad gcphase")

        case _GCoff, _GCquiesce, _GCstw, _GCsweep, _GCscan:
                // ok

        case _GCmark, _GCmarktermination:
                if ptr != 0 && inheap(ptr) {
                        shade(ptr)
                }
        }
}

// The gp has been moved to a GC safepoint. GC phase specific
// work is done here.
func gcphasework(gp *g) {
        switch gcphase {
        default:
                gothrow("gcphasework in bad gcphase")
        case _GCoff, _GCquiesce, _GCstw, _GCsweep:
                // No work.
        case _GCscan:
                // scan the stack, mark the objects, put pointers in work buffers
                // hanging off the P where this is being run.
                scanstack(gp)
        case _GCmark:
                // No work.
        case _GCmarktermination:
                scanstack(gp)
                // All available mark work will be emptied before returning.
        }
        gp.gcworkdone = true
}

var finalizer1 = [...]byte{
        // Each Finalizer is 5 words, ptr ptr uintptr ptr ptr.
        // Each byte describes 4 words.
        // Need 4 Finalizers described by 5 bytes before pattern repeats:
        //      ptr ptr uintptr ptr ptr
        //      ptr ptr uintptr ptr ptr
        //      ptr ptr uintptr ptr ptr
        //      ptr ptr uintptr ptr ptr
        // aka
        //      ptr ptr uintptr ptr
        //      ptr ptr ptr uintptr
        //      ptr ptr ptr ptr
        //      uintptr ptr ptr ptr
        //      ptr uintptr ptr ptr
        // Assumptions about Finalizer layout checked below.
        bitsPointer | bitsPointer<<2 | bitsScalar<<4 | bitsPointer<<6,
        bitsPointer | bitsPointer<<2 | bitsPointer<<4 | bitsScalar<<6,
        bitsPointer | bitsPointer<<2 | bitsPointer<<4 | bitsPointer<<6,
        bitsScalar | bitsPointer<<2 | bitsPointer<<4 | bitsPointer<<6,
        bitsPointer | bitsScalar<<2 | bitsPointer<<4 | bitsPointer<<6,
}

func queuefinalizer(p unsafe.Pointer, fn *funcval, nret uintptr, fint *_type, ot *ptrtype) {
        lock(&finlock)
        if finq == nil || finq.cnt == finq.cap {
                if finc == nil {
                        finc = (*finblock)(persistentalloc(_FinBlockSize, 0, &memstats.gc_sys))
                        finc.cap = int32((_FinBlockSize-unsafe.Sizeof(finblock{}))/unsafe.Sizeof(finalizer{}) + 1)
                        finc.alllink = allfin
                        allfin = finc
                        if finptrmask[0] == 0 {
                                // Build pointer mask for Finalizer array in block.
                                // Check assumptions made in finalizer1 array above.
                                if (unsafe.Sizeof(finalizer{}) != 5*ptrSize ||
                                        unsafe.Offsetof(finalizer{}.fn) != 0 ||
                                        unsafe.Offsetof(finalizer{}.arg) != ptrSize ||
                                        unsafe.Offsetof(finalizer{}.nret) != 2*ptrSize ||
                                        unsafe.Offsetof(finalizer{}.fint) != 3*ptrSize ||
                                        unsafe.Offsetof(finalizer{}.ot) != 4*ptrSize ||
                                        bitsPerPointer != 2) {
                                        gothrow("finalizer out of sync")
                                }
                                for i := range finptrmask {
                                        finptrmask[i] = finalizer1[i%len(finalizer1)]
                                }
                        }
                }
                block := finc
                finc = block.next
                block.next = finq
                finq = block
        }
        f := (*finalizer)(add(unsafe.Pointer(&finq.fin[0]), uintptr(finq.cnt)*unsafe.Sizeof(finq.fin[0])))
        finq.cnt++
        f.fn = fn
        f.nret = nret
        f.fint = fint
        f.ot = ot
        f.arg = p
        fingwake = true
        unlock(&finlock)
}

func iterate_finq(callback func(*funcval, unsafe.Pointer, uintptr, *_type, *ptrtype)) {
        for fb := allfin; fb != nil; fb = fb.alllink {
                for i := int32(0); i < fb.cnt; i++ {
                        f := &fb.fin[i]
                        callback(f.fn, f.arg, f.nret, f.fint, f.ot)
                }
        }
}

// Returns only when span s has been swept.
func mSpan_EnsureSwept(s *mspan) {
        // Caller must disable preemption.
        // Otherwise when this function returns the span can become unswept again
        // (if GC is triggered on another goroutine).
        _g_ := getg()
        if _g_.m.locks == 0 && _g_.m.mallocing == 0 && _g_ != _g_.m.g0 {
                gothrow("MSpan_EnsureSwept: m is not locked")
        }

        sg := mheap_.sweepgen
        if atomicload(&s.sweepgen) == sg {
                return
        }
        // The caller must be sure that the span is a MSpanInUse span.
        if cas(&s.sweepgen, sg-2, sg-1) {
                mSpan_Sweep(s, false)
                return
        }
        // unfortunate condition, and we don't have efficient means to wait
        for atomicload(&s.sweepgen) != sg {
                osyield()
        }
}

// Sweep frees or collects finalizers for blocks not marked in the mark phase.
// It clears the mark bits in preparation for the next GC round.
// Returns true if the span was returned to heap.
// If preserve=true, don't return it to heap nor relink in MCentral lists;
// caller takes care of it.
func mSpan_Sweep(s *mspan, preserve bool) bool {
        if checkmark {
                gothrow("MSpan_Sweep: checkmark only runs in STW and after the sweep")
        }

        // It's critical that we enter this function with preemption disabled,
        // GC must not start while we are in the middle of this function.
        _g_ := getg()
        if _g_.m.locks == 0 && _g_.m.mallocing == 0 && _g_ != _g_.m.g0 {
                gothrow("MSpan_Sweep: m is not locked")
        }
        sweepgen := mheap_.sweepgen
        if s.state != mSpanInUse || s.sweepgen != sweepgen-1 {
                print("MSpan_Sweep: state=", s.state, " sweepgen=", s.sweepgen, " mheap.sweepgen=", sweepgen, "\n")
                gothrow("MSpan_Sweep: bad span state")
        }
        arena_start := mheap_.arena_start
        cl := s.sizeclass
        size := s.elemsize
        var n int32
        var npages int32
        if cl == 0 {
                n = 1
        } else {
                // Chunk full of small blocks.
                npages = class_to_allocnpages[cl]
                n = (npages << _PageShift) / int32(size)
        }
        res := false
        nfree := 0
        var head mlink
        end := &head
        c := _g_.m.mcache
        sweepgenset := false

        // Mark any free objects in this span so we don't collect them.
        for link := s.freelist; link != nil; link = link.next {
                off := (uintptr(unsafe.Pointer(link)) - arena_start) / ptrSize
                bitp := arena_start - off/wordsPerBitmapByte - 1
                shift := (off % wordsPerBitmapByte) * gcBits
                *(*byte)(unsafe.Pointer(bitp)) |= bitMarked << shift
        }

        // Unlink & free special records for any objects we're about to free.
        specialp := &s.specials
        special := *specialp
        for special != nil {
                // A finalizer can be set for an inner byte of an object, find object beginning.
                p := uintptr(s.start<<_PageShift) + uintptr(special.offset)/size*size
                off := (p - arena_start) / ptrSize
                bitp := arena_start - off/wordsPerBitmapByte - 1
                shift := (off % wordsPerBitmapByte) * gcBits
                bits := (*(*byte)(unsafe.Pointer(bitp)) >> shift) & bitMask
                if bits&bitMarked == 0 {
                        // Find the exact byte for which the special was setup
                        // (as opposed to object beginning).
                        p := uintptr(s.start<<_PageShift) + uintptr(special.offset)
                        // about to free object: splice out special record
                        y := special
                        special = special.next
                        *specialp = special
                        if !freespecial(y, unsafe.Pointer(p), size, false) {
                                // stop freeing of object if it has a finalizer
                                *(*byte)(unsafe.Pointer(bitp)) |= bitMarked << shift
                        }
                } else {
                        // object is still live: keep special record
                        specialp = &special.next
                        special = *specialp
                }
        }

        // Sweep through n objects of given size starting at p.
        // This thread owns the span now, so it can manipulate
        // the block bitmap without atomic operations.
        p := uintptr(s.start << _PageShift)
        off := (p - arena_start) / ptrSize
        bitp := arena_start - off/wordsPerBitmapByte - 1
        shift := uint(0)
        step := size / (ptrSize * wordsPerBitmapByte)
        // Rewind to the previous quadruple as we move to the next
        // in the beginning of the loop.
        bitp += step
        if step == 0 {
                // 8-byte objects.
                bitp++
                shift = gcBits
        }
        for ; n > 0; n, p = n-1, p+size {
                bitp -= step
                if step == 0 {
                        if shift != 0 {
                                bitp--
                        }
                        shift = gcBits - shift
                }

                xbits := *(*byte)(unsafe.Pointer(bitp))
                bits := (xbits >> shift) & bitMask

                // Allocated and marked object, reset bits to allocated.
                if bits&bitMarked != 0 {
                        *(*byte)(unsafe.Pointer(bitp)) &^= bitMarked << shift
                        continue
                }

                // At this point we know that we are looking at garbage object
                // that needs to be collected.
                if debug.allocfreetrace != 0 {
                        tracefree(unsafe.Pointer(p), size)
                }

                // Reset to allocated+noscan.
                *(*byte)(unsafe.Pointer(bitp)) = uint8(uintptr(xbits&^((bitMarked|bitsMask<<2)<<shift)) | uintptr(bitsDead)<<(shift+2))
                if cl == 0 {
                        // Free large span.
                        if preserve {
                                gothrow("can't preserve large span")
                        }
                        unmarkspan(p, s.npages<<_PageShift)
                        s.needzero = 1

                        // important to set sweepgen before returning it to heap
                        atomicstore(&s.sweepgen, sweepgen)
                        sweepgenset = true

                        // NOTE(rsc,dvyukov): The original implementation of efence
                        // in CL 22060046 used SysFree instead of SysFault, so that
                        // the operating system would eventually give the memory
                        // back to us again, so that an efence program could run
                        // longer without running out of memory. Unfortunately,
                        // calling SysFree here without any kind of adjustment of the
                        // heap data structures means that when the memory does
                        // come back to us, we have the wrong metadata for it, either in
                        // the MSpan structures or in the garbage collection bitmap.
                        // Using SysFault here means that the program will run out of
                        // memory fairly quickly in efence mode, but at least it won't
                        // have mysterious crashes due to confused memory reuse.
                        // It should be possible to switch back to SysFree if we also
                        // implement and then call some kind of MHeap_DeleteSpan.
                        if debug.efence > 0 {
                                s.limit = 0 // prevent mlookup from finding this span
                                sysFault(unsafe.Pointer(p), size)
                        } else {
                                mHeap_Free(&mheap_, s, 1)
                        }
                        c.local_nlargefree++
                        c.local_largefree += size
                        xadd64(&memstats.next_gc, -int64(size)*int64(gcpercent+100)/100)
                        res = true
                } else {
                        // Free small object.
                        if size > 2*ptrSize {
                                *(*uintptr)(unsafe.Pointer(p + ptrSize)) = uintptrMask & 0xdeaddeaddeaddead // mark as "needs to be zeroed"
                        } else if size > ptrSize {
                                *(*uintptr)(unsafe.Pointer(p + ptrSize)) = 0
                        }
                        end.next = (*mlink)(unsafe.Pointer(p))
                        end = end.next
                        nfree++
                }
        }

        // We need to set s.sweepgen = h.sweepgen only when all blocks are swept,
        // because of the potential for a concurrent free/SetFinalizer.
        // But we need to set it before we make the span available for allocation
        // (return it to heap or mcentral), because allocation code assumes that a
        // span is already swept if available for allocation.
        if !sweepgenset && nfree == 0 {
                // The span must be in our exclusive ownership until we update sweepgen,
                // check for potential races.
                if s.state != mSpanInUse || s.sweepgen != sweepgen-1 {
                        print("MSpan_Sweep: state=", s.state, " sweepgen=", s.sweepgen, " mheap.sweepgen=", sweepgen, "\n")
                        gothrow("MSpan_Sweep: bad span state after sweep")
                }
                atomicstore(&s.sweepgen, sweepgen)
        }
        if nfree > 0 {
                c.local_nsmallfree[cl] += uintptr(nfree)
                c.local_cachealloc -= intptr(uintptr(nfree) * size)
                xadd64(&memstats.next_gc, -int64(nfree)*int64(size)*int64(gcpercent+100)/100)
                res = mCentral_FreeSpan(&mheap_.central[cl].mcentral, s, int32(nfree), head.next, end, preserve)
                // MCentral_FreeSpan updates sweepgen
        }
        return res
}

// State of background sweep.
// Protected by gclock.
type sweepdata struct {
        g       *g
        parked  bool
        started bool

        spanidx uint32 // background sweeper position

        nbgsweep    uint32
        npausesweep uint32
}

var sweep sweepdata

// sweeps one span
// returns number of pages returned to heap, or ^uintptr(0) if there is nothing to sweep
func sweepone() uintptr {
        _g_ := getg()

        // increment locks to ensure that the goroutine is not preempted
        // in the middle of sweep thus leaving the span in an inconsistent state for next GC
        _g_.m.locks++
        sg := mheap_.sweepgen
        for {
                idx := xadd(&sweep.spanidx, 1) - 1
                if idx >= uint32(len(work.spans)) {
                        mheap_.sweepdone = 1
                        _g_.m.locks--
                        return ^uintptr(0)
                }
                s := work.spans[idx]
                if s.state != mSpanInUse {
                        s.sweepgen = sg
                        continue
                }
                if s.sweepgen != sg-2 || !cas(&s.sweepgen, sg-2, sg-1) {
                        continue
                }
                npages := s.npages
                if !mSpan_Sweep(s, false) {
                        npages = 0
                }
                _g_.m.locks--
                return npages
        }
}

func gosweepone() uintptr {
        var ret uintptr
        systemstack(func() {
                ret = sweepone()
        })
        return ret
}

func gosweepdone() bool {
        return mheap_.sweepdone != 0
}

func gchelper() {
        _g_ := getg()
        _g_.m.traceback = 2
        gchelperstart()

        // parallel mark for over GC roots
        parfordo(work.markfor)
        if gcphase != _GCscan {
                scanblock(0, 0, nil) // blocks in getfull
        }

        nproc := work.nproc // work.nproc can change right after we increment work.ndone
        if xadd(&work.ndone, +1) == nproc-1 {
                notewakeup(&work.alldone)
        }
        _g_.m.traceback = 0
}

func cachestats() {
        for i := 0; ; i++ {
                p := allp[i]
                if p == nil {
                        break
                }
                c := p.mcache
                if c == nil {
                        continue
                }
                purgecachedstats(c)
        }
}

func flushallmcaches() {
        for i := 0; ; i++ {
                p := allp[i]
                if p == nil {
                        break
                }
                c := p.mcache
                if c == nil {
                        continue
                }
                mCache_ReleaseAll(c)
                stackcache_clear(c)
        }
}

func updatememstats(stats *gcstats) {
        if stats != nil {
                *stats = gcstats{}
        }
        for mp := allm; mp != nil; mp = mp.alllink {
                if stats != nil {
                        src := (*[unsafe.Sizeof(gcstats{}) / 8]uint64)(unsafe.Pointer(&mp.gcstats))
                        dst := (*[unsafe.Sizeof(gcstats{}) / 8]uint64)(unsafe.Pointer(stats))
                        for i, v := range src {
                                dst[i] += v
                        }
                        mp.gcstats = gcstats{}
                }
        }

        memstats.mcache_inuse = uint64(mheap_.cachealloc.inuse)
        memstats.mspan_inuse = uint64(mheap_.spanalloc.inuse)
        memstats.sys = memstats.heap_sys + memstats.stacks_sys + memstats.mspan_sys +
                memstats.mcache_sys + memstats.buckhash_sys + memstats.gc_sys + memstats.other_sys

        // Calculate memory allocator stats.
        // During program execution we only count number of frees and amount of freed memory.
        // Current number of alive object in the heap and amount of alive heap memory
        // are calculated by scanning all spans.
        // Total number of mallocs is calculated as number of frees plus number of alive objects.
        // Similarly, total amount of allocated memory is calculated as amount of freed memory
        // plus amount of alive heap memory.
        memstats.alloc = 0
        memstats.total_alloc = 0
        memstats.nmalloc = 0
        memstats.nfree = 0
        for i := 0; i < len(memstats.by_size); i++ {
                memstats.by_size[i].nmalloc = 0
                memstats.by_size[i].nfree = 0
        }

        // Flush MCache's to MCentral.
        systemstack(flushallmcaches)

        // Aggregate local stats.
        cachestats()

        // Scan all spans and count number of alive objects.
        lock(&mheap_.lock)
        for i := uint32(0); i < mheap_.nspan; i++ {
                s := h_allspans[i]
                if s.state != mSpanInUse {
                        continue
                }
                if s.sizeclass == 0 {
                        memstats.nmalloc++
                        memstats.alloc += uint64(s.elemsize)
                } else {
                        memstats.nmalloc += uint64(s.ref)
                        memstats.by_size[s.sizeclass].nmalloc += uint64(s.ref)
                        memstats.alloc += uint64(s.ref) * uint64(s.elemsize)
                }
        }
        unlock(&mheap_.lock)

        // Aggregate by size class.
        smallfree := uint64(0)
        memstats.nfree = mheap_.nlargefree
        for i := 0; i < len(memstats.by_size); i++ {
                memstats.nfree += mheap_.nsmallfree[i]
                memstats.by_size[i].nfree = mheap_.nsmallfree[i]
                memstats.by_size[i].nmalloc += mheap_.nsmallfree[i]
                smallfree += uint64(mheap_.nsmallfree[i]) * uint64(class_to_size[i])
        }
        memstats.nfree += memstats.tinyallocs
        memstats.nmalloc += memstats.nfree

        // Calculate derived stats.
        memstats.total_alloc = uint64(memstats.alloc) + uint64(mheap_.largefree) + smallfree
        memstats.heap_alloc = memstats.alloc
        memstats.heap_objects = memstats.nmalloc - memstats.nfree
}

func gcinit() {
        if unsafe.Sizeof(workbuf{}) != _WorkbufSize {
                gothrow("runtime: size of Workbuf is suboptimal")
        }

        work.markfor = parforalloc(_MaxGcproc)
        gcpercent = readgogc()
        gcdatamask = unrollglobgcprog((*byte)(unsafe.Pointer(&gcdata)), uintptr(unsafe.Pointer(&edata))-uintptr(unsafe.Pointer(&data)))
        gcbssmask = unrollglobgcprog((*byte)(unsafe.Pointer(&gcbss)), uintptr(unsafe.Pointer(&ebss))-uintptr(unsafe.Pointer(&bss)))
}

// Called from malloc.go using onM, stopping and starting the world handled in caller.
func gc_m(start_time int64, eagersweep bool) {
        _g_ := getg()
        gp := _g_.m.curg
        casgstatus(gp, _Grunning, _Gwaiting)
        gp.waitreason = "garbage collection"

        gc(start_time, eagersweep)
        casgstatus(gp, _Gwaiting, _Grunning)
}

// Similar to clearcheckmarkbits but works on a single span.
// It preforms two tasks.
// 1. When used before the checkmark phase it converts BitsDead (00) to bitsScalar (01)
//    for nibbles with the BoundaryBit set.
// 2. When used after the checkmark phase it converts BitsPointerMark (11) to BitsPointer 10 and
//    BitsScalarMark (00) to BitsScalar (01), thus clearing the checkmark mark encoding.
// For the second case it is possible to restore the BitsDead pattern but since
// clearmark is a debug tool performance has a lower priority than simplicity.
// The span is MSpanInUse and the world is stopped.
func clearcheckmarkbitsspan(s *mspan) {
        if s.state != _MSpanInUse {
                print("runtime:clearcheckmarkbitsspan: state=", s.state, "\n")
                gothrow("clearcheckmarkbitsspan: bad span state")
        }

        arena_start := mheap_.arena_start
        cl := s.sizeclass
        size := s.elemsize
        var n int32
        if cl == 0 {
                n = 1
        } else {
                // Chunk full of small blocks
                npages := class_to_allocnpages[cl]
                n = npages << _PageShift / int32(size)
        }

        // MSpan_Sweep has similar code but instead of overloading and
        // complicating that routine we do a simpler walk here.
        // Sweep through n objects of given size starting at p.
        // This thread owns the span now, so it can manipulate
        // the block bitmap without atomic operations.
        p := uintptr(s.start) << _PageShift

        // Find bits for the beginning of the span.
        off := (p - arena_start) / ptrSize
        bitp := (*byte)(unsafe.Pointer(arena_start - off/wordsPerBitmapByte - 1))
        step := size / (ptrSize * wordsPerBitmapByte)

        // The type bit values are:
        //      00 - BitsDead, for us BitsScalarMarked
        //      01 - BitsScalar
        //      10 - BitsPointer
        //      11 - unused, for us BitsPointerMarked
        //
        // When called to prepare for the checkmark phase (checkmark==1),
        // we change BitsDead to BitsScalar, so that there are no BitsScalarMarked
        // type bits anywhere.
        //
        // The checkmark phase marks by changing BitsScalar to BitsScalarMarked
        // and BitsPointer to BitsPointerMarked.
        //
        // When called to clean up after the checkmark phase (checkmark==0),
        // we unmark by changing BitsScalarMarked back to BitsScalar and
        // BitsPointerMarked back to BitsPointer.
        //
        // There are two problems with the scheme as just described.
        // First, the setup rewrites BitsDead to BitsScalar, but the type bits
        // following a BitsDead are uninitialized and must not be used.
        // Second, objects that are free are expected to have their type
        // bits zeroed (BitsDead), so in the cleanup we need to restore
        // any BitsDeads that were there originally.
        //
        // In a one-word object (8-byte allocation on 64-bit system),
        // there is no difference between BitsScalar and BitsDead, because
        // neither is a pointer and there are no more words in the object,
        // so using BitsScalar during the checkmark is safe and mapping
        // both back to BitsDead during cleanup is also safe.
        //
        // In a larger object, we need to be more careful. During setup,
        // if the type of the first word is BitsDead, we change it to BitsScalar
        // (as we must) but also initialize the type of the second
        // word to BitsDead, so that a scan during the checkmark phase
        // will still stop before seeing the uninitialized type bits in the
        // rest of the object. The sequence 'BitsScalar BitsDead' never
        // happens in real type bitmaps - BitsDead is always as early
        // as possible, so immediately after the last BitsPointer.
        // During cleanup, if we see a BitsScalar, we can check to see if it
        // is followed by BitsDead. If so, it was originally BitsDead and
        // we can change it back.

        if step == 0 {
                // updating top and bottom nibbles, all boundaries
                for i := int32(0); i < n/2; i, bitp = i+1, addb(bitp, uintptrMask&-1) {
                        if *bitp&bitBoundary == 0 {
                                gothrow("missing bitBoundary")
                        }
                        b := (*bitp & bitPtrMask) >> 2
                        if !checkmark && (b == _BitsScalar || b == _BitsScalarMarked) {
                                *bitp &^= 0x0c // convert to _BitsDead
                        } else if b == _BitsScalarMarked || b == _BitsPointerMarked {
                                *bitp &^= _BitsCheckMarkXor << 2
                        }

                        if (*bitp>>gcBits)&bitBoundary == 0 {
                                gothrow("missing bitBoundary")
                        }
                        b = ((*bitp >> gcBits) & bitPtrMask) >> 2
                        if !checkmark && (b == _BitsScalar || b == _BitsScalarMarked) {
                                *bitp &^= 0xc0 // convert to _BitsDead
                        } else if b == _BitsScalarMarked || b == _BitsPointerMarked {
                                *bitp &^= _BitsCheckMarkXor << (2 + gcBits)
                        }
                }
        } else {
                // updating bottom nibble for first word of each object
                for i := int32(0); i < n; i, bitp = i+1, addb(bitp, -step) {
                        if *bitp&bitBoundary == 0 {
                                gothrow("missing bitBoundary")
                        }
                        b := (*bitp & bitPtrMask) >> 2

                        if checkmark && b == _BitsDead {
                                // move BitsDead into second word.
                                // set bits to BitsScalar in preparation for checkmark phase.
                                *bitp &^= 0xc0
                                *bitp |= _BitsScalar << 2
                        } else if !checkmark && (b == _BitsScalar || b == _BitsScalarMarked) && *bitp&0xc0 == 0 {
                                // Cleaning up after checkmark phase.
                                // First word is scalar or dead (we forgot)
                                // and second word is dead.
                                // First word might as well be dead too.
                                *bitp &^= 0x0c
                        } else if b == _BitsScalarMarked || b == _BitsPointerMarked {
                                *bitp ^= _BitsCheckMarkXor << 2
                        }
                }
        }
}

// clearcheckmarkbits preforms two tasks.
// 1. When used before the checkmark phase it converts BitsDead (00) to bitsScalar (01)
//    for nibbles with the BoundaryBit set.
// 2. When used after the checkmark phase it converts BitsPointerMark (11) to BitsPointer 10 and
//    BitsScalarMark (00) to BitsScalar (01), thus clearing the checkmark mark encoding.
// This is a bit expensive but preserves the BitsDead encoding during the normal marking.
// BitsDead remains valid for every nibble except the ones with BitsBoundary set.
func clearcheckmarkbits() {
        for _, s := range work.spans {
                if s.state == _MSpanInUse {
                        clearcheckmarkbitsspan(s)
                }
        }
}

// Called from malloc.go using onM.
// The world is stopped. Rerun the scan and mark phases
// using the bitMarkedCheck bit instead of the
// bitMarked bit. If the marking encounters an
// bitMarked bit that is not set then we throw.
func gccheckmark_m(startTime int64, eagersweep bool) {
        if !gccheckmarkenable {
                return
        }

        if checkmark {
                gothrow("gccheckmark_m, entered with checkmark already true")
        }

        checkmark = true
        clearcheckmarkbits()        // Converts BitsDead to BitsScalar.
        gc_m(startTime, eagersweep) // turns off checkmark
        // Work done, fixed up the GC bitmap to remove the checkmark bits.
        clearcheckmarkbits()
}

func gccheckmarkenable_m() {
        gccheckmarkenable = true
}

func gccheckmarkdisable_m() {
        gccheckmarkenable = false
}

func finishsweep_m() {
        // The world is stopped so we should be able to complete the sweeps
        // quickly.
        for sweepone() != ^uintptr(0) {
                sweep.npausesweep++
        }

        // There may be some other spans being swept concurrently that
        // we need to wait for. If finishsweep_m is done with the world stopped
        // this code is not required.
        sg := mheap_.sweepgen
        for _, s := range work.spans {
                if s.sweepgen != sg && s.state == _MSpanInUse {
                        mSpan_EnsureSwept(s)
                }
        }
}

// Scan all of the stacks, greying (or graying if in America) the referents
// but not blackening them since the mark write barrier isn't installed.
func gcscan_m() {
        _g_ := getg()

        // Grab the g that called us and potentially allow rescheduling.
        // This allows it to be scanned like other goroutines.
        mastergp := _g_.m.curg
        casgstatus(mastergp, _Grunning, _Gwaiting)
        mastergp.waitreason = "garbage collection scan"

        // Span sweeping has been done by finishsweep_m.
        // Long term we will want to make this goroutine runnable
        // by placing it onto a scanenqueue state and then calling
        // runtime·restartg(mastergp) to make it Grunnable.
        // At the bottom we will want to return this p back to the scheduler.
        oldphase := gcphase

        // Prepare flag indicating that the scan has not been completed.
        lock(&allglock)
        local_allglen := allglen
        for i := uintptr(0); i < local_allglen; i++ {
                gp := allgs[i]
                gp.gcworkdone = false // set to true in gcphasework
        }
        unlock(&allglock)

        work.nwait = 0
        work.ndone = 0
        work.nproc = 1 // For now do not do this in parallel.
        gcphase = _GCscan
        //      ackgcphase is not needed since we are not scanning running goroutines.
        parforsetup(work.markfor, work.nproc, uint32(_RootCount+local_allglen), nil, false, markroot)
        parfordo(work.markfor)

        lock(&allglock)
        // Check that gc work is done.
        for i := uintptr(0); i < local_allglen; i++ {
                gp := allgs[i]
                if !gp.gcworkdone {
                        gothrow("scan missed a g")
                }
        }
        unlock(&allglock)

        gcphase = oldphase
        casgstatus(mastergp, _Gwaiting, _Grunning)
        // Let the g that called us continue to run.
}

// Mark all objects that are known about.
func gcmark_m() {
        scanblock(0, 0, nil)
}

// For now this must be bracketed with a stoptheworld and a starttheworld to ensure
// all go routines see the new barrier.
func gcinstallmarkwb_m() {
        gcphase = _GCmark
}

// For now this must be bracketed with a stoptheworld and a starttheworld to ensure
// all go routines see the new barrier.
func gcinstalloffwb_m() {
        gcphase = _GCoff
}

func gc(start_time int64, eagersweep bool) {
        if _DebugGCPtrs {
                print("GC start\n")
        }

        if debug.allocfreetrace > 0 {
                tracegc()
        }

        _g_ := getg()
        _g_.m.traceback = 2
        t0 := start_time
        work.tstart = start_time

        var t1 int64
        if debug.gctrace > 0 {
                t1 = nanotime()
        }

        if !checkmark {
                finishsweep_m() // skip during checkmark debug phase.
        }

        // Cache runtime.mheap_.allspans in work.spans to avoid conflicts with
        // resizing/freeing allspans.
        // New spans can be created while GC progresses, but they are not garbage for
        // this round:
        //  - new stack spans can be created even while the world is stopped.
        //  - new malloc spans can be created during the concurrent sweep

        // Even if this is stop-the-world, a concurrent exitsyscall can allocate a stack from heap.
        lock(&mheap_.lock)
        // Free the old cached sweep array if necessary.
        if work.spans != nil && &work.spans[0] != &h_allspans[0] {
                sysFree(unsafe.Pointer(&work.spans[0]), uintptr(len(work.spans))*unsafe.Sizeof(work.spans[0]), &memstats.other_sys)
        }
        // Cache the current array for marking.
        mheap_.gcspans = mheap_.allspans
        work.spans = h_allspans
        unlock(&mheap_.lock)
        oldphase := gcphase

        work.nwait = 0
        work.ndone = 0
        work.nproc = uint32(gcprocs())
        gcphase = _GCmarktermination

        // World is stopped so allglen will not change.
        for i := uintptr(0); i < allglen; i++ {
                gp := allgs[i]
                gp.gcworkdone = false // set to true in gcphasework
        }

        parforsetup(work.markfor, work.nproc, uint32(_RootCount+allglen), nil, false, markroot)
        if work.nproc > 1 {
                noteclear(&work.alldone)
                helpgc(int32(work.nproc))
        }

        var t2 int64
        if debug.gctrace > 0 {
                t2 = nanotime()
        }

        gchelperstart()
        parfordo(work.markfor)
        scanblock(0, 0, nil)

        if work.full != 0 {
                gothrow("work.full != 0")
        }
        if work.partial != 0 {
                gothrow("work.partial != 0")
        }

        gcphase = oldphase
        var t3 int64
        if debug.gctrace > 0 {
                t3 = nanotime()
        }

        if work.nproc > 1 {
                notesleep(&work.alldone)
        }

        shrinkfinish()

        cachestats()
        // next_gc calculation is tricky with concurrent sweep since we don't know size of live heap
        // estimate what was live heap size after previous GC (for printing only)
        heap0 := memstats.next_gc * 100 / (uint64(gcpercent) + 100)
        // conservatively set next_gc to high value assuming that everything is live
        // concurrent/lazy sweep will reduce this number while discovering new garbage
        memstats.next_gc = memstats.heap_alloc + memstats.heap_alloc*uint64(gcpercent)/100

        t4 := nanotime()
        atomicstore64(&memstats.last_gc, uint64(unixnanotime())) // must be Unix time to make sense to user
        memstats.pause_ns[memstats.numgc%uint32(len(memstats.pause_ns))] = uint64(t4 - t0)
        memstats.pause_end[memstats.numgc%uint32(len(memstats.pause_end))] = uint64(t4)
        memstats.pause_total_ns += uint64(t4 - t0)
        memstats.numgc++
        if memstats.debuggc {
                print("pause ", t4-t0, "\n")
        }

        if debug.gctrace > 0 {
                heap1 := memstats.heap_alloc
                var stats gcstats
                updatememstats(&stats)
                if heap1 != memstats.heap_alloc {
                        print("runtime: mstats skew: heap=", heap1, "/", memstats.heap_alloc, "\n")
                        gothrow("mstats skew")
                }
                obj := memstats.nmalloc - memstats.nfree

                stats.nprocyield += work.markfor.nprocyield
                stats.nosyield += work.markfor.nosyield
                stats.nsleep += work.markfor.nsleep

                print("gc", memstats.numgc, "(", work.nproc, "): ",
                        (t1-t0)/1000, "+", (t2-t1)/1000, "+", (t3-t2)/1000, "+", (t4-t3)/1000, " us, ",
                        heap0>>20, " -> ", heap1>>20, " MB, ",
                        obj, " (", memstats.nmalloc, "-", memstats.nfree, ") objects, ",
                        gcount(), " goroutines, ",
                        len(work.spans), "/", sweep.nbgsweep, "/", sweep.npausesweep, " sweeps, ",
                        stats.nhandoff, "(", stats.nhandoffcnt, ") handoff, ",
                        work.markfor.nsteal, "(", work.markfor.nstealcnt, ") steal, ",
                        stats.nprocyield, "/", stats.nosyield, "/", stats.nsleep, " yields\n")
                sweep.nbgsweep = 0
                sweep.npausesweep = 0
        }

        // See the comment in the beginning of this function as to why we need the following.
        // Even if this is still stop-the-world, a concurrent exitsyscall can allocate a stack from heap.
        lock(&mheap_.lock)
        // Free the old cached mark array if necessary.
        if work.spans != nil && &work.spans[0] != &h_allspans[0] {
                sysFree(unsafe.Pointer(&work.spans[0]), uintptr(len(work.spans))*unsafe.Sizeof(work.spans[0]), &memstats.other_sys)
        }

        if gccheckmarkenable {
                if !checkmark {
                        // first half of two-pass; don't set up sweep
                        unlock(&mheap_.lock)
                        return
                }
                checkmark = false // done checking marks
        }

        // Cache the current array for sweeping.
        mheap_.gcspans = mheap_.allspans
        mheap_.sweepgen += 2
        mheap_.sweepdone = 0
        work.spans = h_allspans
        sweep.spanidx = 0
        unlock(&mheap_.lock)

        if _ConcurrentSweep && !eagersweep {
                lock(&gclock)
                if !sweep.started {
                        go bgsweep()
                        sweep.started = true
                } else if sweep.parked {
                        sweep.parked = false
                        ready(sweep.g)
                }
                unlock(&gclock)
        } else {
                // Sweep all spans eagerly.
                for sweepone() != ^uintptr(0) {
                        sweep.npausesweep++
                }
                // Do an additional mProf_GC, because all 'free' events are now real as well.
                mProf_GC()
        }

        mProf_GC()
        _g_.m.traceback = 0

        if _DebugGCPtrs {
                print("GC end\n")
        }
}

func readmemstats_m(stats *MemStats) {
        updatememstats(nil)

        // Size of the trailing by_size array differs between Go and C,
        // NumSizeClasses was changed, but we can not change Go struct because of backward compatibility.
        memmove(unsafe.Pointer(stats), unsafe.Pointer(&memstats), sizeof_C_MStats)

        // Stack numbers are part of the heap numbers, separate those out for user consumption
        stats.StackSys = stats.StackInuse
        stats.HeapInuse -= stats.StackInuse
        stats.HeapSys -= stats.StackInuse
}

//go:linkname readGCStats runtime/debug.readGCStats
func readGCStats(pauses *[]uint64) {
        systemstack(func() {
                readGCStats_m(pauses)
        })
}

func readGCStats_m(pauses *[]uint64) {
        p := *pauses
        // Calling code in runtime/debug should make the slice large enough.
        if cap(p) < len(memstats.pause_ns)+3 {
                gothrow("runtime: short slice passed to readGCStats")
        }

        // Pass back: pauses, pause ends, last gc (absolute time), number of gc, total pause ns.
        lock(&mheap_.lock)

        n := memstats.numgc
        if n > uint32(len(memstats.pause_ns)) {
                n = uint32(len(memstats.pause_ns))
        }

        // The pause buffer is circular. The most recent pause is at
        // pause_ns[(numgc-1)%len(pause_ns)], and then backward
        // from there to go back farther in time. We deliver the times
        // most recent first (in p[0]).
        p = p[:cap(p)]
        for i := uint32(0); i < n; i++ {
                j := (memstats.numgc - 1 - i) % uint32(len(memstats.pause_ns))
                p[i] = memstats.pause_ns[j]
                p[n+i] = memstats.pause_end[j]
        }

        p[n+n] = memstats.last_gc
        p[n+n+1] = uint64(memstats.numgc)
        p[n+n+2] = memstats.pause_total_ns
        unlock(&mheap_.lock)
        *pauses = p[:n+n+3]
}

func setGCPercent(in int32) (out int32) {
        lock(&mheap_.lock)
        out = gcpercent
        if in < 0 {
                in = -1
        }
        gcpercent = in
        unlock(&mheap_.lock)
        return out
}

func gchelperstart() {
        _g_ := getg()

        if _g_.m.helpgc < 0 || _g_.m.helpgc >= _MaxGcproc {
                gothrow("gchelperstart: bad m->helpgc")
        }
        if _g_ != _g_.m.g0 {
                gothrow("gchelper not running on g0 stack")
        }
}

func wakefing() *g {
        var res *g
        lock(&finlock)
        if fingwait && fingwake {
                fingwait = false
                fingwake = false
                res = fing
        }
        unlock(&finlock)
        return res
}

func addb(p *byte, n uintptr) *byte {
        return (*byte)(add(unsafe.Pointer(p), n))
}

// Recursively unrolls GC program in prog.
// mask is where to store the result.
// ppos is a pointer to position in mask, in bits.
// sparse says to generate 4-bits per word mask for heap (2-bits for data/bss otherwise).
func unrollgcprog1(maskp *byte, prog *byte, ppos *uintptr, inplace, sparse bool) *byte {
        arena_start := mheap_.arena_start
        pos := *ppos
        mask := (*[1 << 30]byte)(unsafe.Pointer(maskp))
        for {
                switch *prog {
                default:
                        gothrow("unrollgcprog: unknown instruction")

                case insData:
                        prog = addb(prog, 1)
                        siz := int(*prog)
                        prog = addb(prog, 1)
                        p := (*[1 << 30]byte)(unsafe.Pointer(prog))
                        for i := 0; i < siz; i++ {
                                v := p[i/_PointersPerByte]
                                v >>= (uint(i) % _PointersPerByte) * _BitsPerPointer
                                v &= _BitsMask
                                if inplace {
                                        // Store directly into GC bitmap.
                                        off := (uintptr(unsafe.Pointer(&mask[pos])) - arena_start) / ptrSize
                                        bitp := (*byte)(unsafe.Pointer(arena_start - off/wordsPerBitmapByte - 1))
                                        shift := (off % wordsPerBitmapByte) * gcBits
                                        if shift == 0 {
                                                *bitp = 0
                                        }
                                        *bitp |= v << (shift + 2)
                                        pos += ptrSize
                                } else if sparse {
                                        // 4-bits per word
                                        v <<= (pos % 8) + 2
                                        mask[pos/8] |= v
                                        pos += gcBits
                                } else {
                                        // 2-bits per word
                                        v <<= pos % 8
                                        mask[pos/8] |= v
                                        pos += _BitsPerPointer
                                }
                        }
                        prog = addb(prog, round(uintptr(siz)*_BitsPerPointer, 8)/8)

                case insArray:
                        prog = (*byte)(add(unsafe.Pointer(prog), 1))
                        siz := uintptr(0)
                        for i := uintptr(0); i < ptrSize; i++ {
                                siz = (siz << 8) + uintptr(*(*byte)(add(unsafe.Pointer(prog), ptrSize-i-1)))
                        }
                        prog = (*byte)(add(unsafe.Pointer(prog), ptrSize))
                        var prog1 *byte
                        for i := uintptr(0); i < siz; i++ {
                                prog1 = unrollgcprog1(&mask[0], prog, &pos, inplace, sparse)
                        }
                        if *prog1 != insArrayEnd {
                                gothrow("unrollgcprog: array does not end with insArrayEnd")
                        }
                        prog = (*byte)(add(unsafe.Pointer(prog1), 1))

                case insArrayEnd, insEnd:
                        *ppos = pos
                        return prog
                }
        }
}

// Unrolls GC program prog for data/bss, returns dense GC mask.
func unrollglobgcprog(prog *byte, size uintptr) bitvector {
        masksize := round(round(size, ptrSize)/ptrSize*bitsPerPointer, 8) / 8
        mask := (*[1 << 30]byte)(persistentalloc(masksize+1, 0, &memstats.gc_sys))
        mask[masksize] = 0xa1
        pos := uintptr(0)
        prog = unrollgcprog1(&mask[0], prog, &pos, false, false)
        if pos != size/ptrSize*bitsPerPointer {
                print("unrollglobgcprog: bad program size, got ", pos, ", expect ", size/ptrSize*bitsPerPointer, "\n")
                gothrow("unrollglobgcprog: bad program size")
        }
        if *prog != insEnd {
                gothrow("unrollglobgcprog: program does not end with insEnd")
        }
        if mask[masksize] != 0xa1 {
                gothrow("unrollglobgcprog: overflow")
        }
        return bitvector{int32(masksize * 8), &mask[0]}
}

func unrollgcproginplace_m(v unsafe.Pointer, typ *_type, size, size0 uintptr) {
        pos := uintptr(0)
        prog := (*byte)(unsafe.Pointer(uintptr(typ.gc[1])))
        for pos != size0 {
                unrollgcprog1((*byte)(v), prog, &pos, true, true)
        }

        // Mark first word as bitAllocated.
        arena_start := mheap_.arena_start
        off := (uintptr(v) - arena_start) / ptrSize
        bitp := (*byte)(unsafe.Pointer(arena_start - off/wordsPerBitmapByte - 1))
        shift := (off % wordsPerBitmapByte) * gcBits
        *bitp |= bitBoundary << shift

        // Mark word after last as BitsDead.
        if size0 < size {
                off := (uintptr(v) + size0 - arena_start) / ptrSize
                bitp := (*byte)(unsafe.Pointer(arena_start - off/wordsPerBitmapByte - 1))
                shift := (off % wordsPerBitmapByte) * gcBits
                *bitp &= uint8(^(bitPtrMask << shift) | uintptr(bitsDead)<<(shift+2))
        }
}

var unroll mutex

// Unrolls GC program in typ.gc[1] into typ.gc[0]
func unrollgcprog_m(typ *_type) {
        lock(&unroll)
        mask := (*byte)(unsafe.Pointer(uintptr(typ.gc[0])))
        if *mask == 0 {
                pos := uintptr(8) // skip the unroll flag
                prog := (*byte)(unsafe.Pointer(uintptr(typ.gc[1])))
                prog = unrollgcprog1(mask, prog, &pos, false, true)
                if *prog != insEnd {
                        gothrow("unrollgcprog: program does not end with insEnd")
                }
                if typ.size/ptrSize%2 != 0 {
                        // repeat the program
                        prog := (*byte)(unsafe.Pointer(uintptr(typ.gc[1])))
                        unrollgcprog1(mask, prog, &pos, false, true)
                }

                // atomic way to say mask[0] = 1
                atomicor8(mask, 1)
        }
        unlock(&unroll)
}

// mark the span of memory at v as having n blocks of the given size.
// if leftover is true, there is left over space at the end of the span.
func markspan(v unsafe.Pointer, size uintptr, n uintptr, leftover bool) {
        if uintptr(v)+size*n > mheap_.arena_used || uintptr(v) < mheap_.arena_start {
                gothrow("markspan: bad pointer")
        }

        // Find bits of the beginning of the span.
        off := (uintptr(v) - uintptr(mheap_.arena_start)) / ptrSize
        if off%wordsPerBitmapByte != 0 {
                gothrow("markspan: unaligned length")
        }
        b := mheap_.arena_start - off/wordsPerBitmapByte - 1

        // Okay to use non-atomic ops here, because we control
        // the entire span, and each bitmap byte has bits for only
        // one span, so no other goroutines are changing these bitmap words.

        if size == ptrSize {
                // Possible only on 64-bits (minimal size class is 8 bytes).
                // Set memory to 0x11.
                if (bitBoundary|bitsDead)<<gcBits|bitBoundary|bitsDead != 0x11 {
                        gothrow("markspan: bad bits")
                }
                if n%(wordsPerBitmapByte*ptrSize) != 0 {
                        gothrow("markspan: unaligned length")
                }
                b = b - n/wordsPerBitmapByte + 1 // find first byte
                if b%ptrSize != 0 {
                        gothrow("markspan: unaligned pointer")
                }
                for i := uintptr(0); i < n; i, b = i+wordsPerBitmapByte*ptrSize, b+ptrSize {
                        *(*uintptr)(unsafe.Pointer(b)) = uintptrMask & 0x1111111111111111 // bitBoundary | bitsDead, repeated
                }
                return
        }

        if leftover {
                n++ // mark a boundary just past end of last block too
        }
        step := size / (ptrSize * wordsPerBitmapByte)
        for i := uintptr(0); i < n; i, b = i+1, b-step {
                *(*byte)(unsafe.Pointer(b)) = bitBoundary | bitsDead<<2
        }
}

// unmark the span of memory at v of length n bytes.
func unmarkspan(v, n uintptr) {
        if v+n > mheap_.arena_used || v < mheap_.arena_start {
                gothrow("markspan: bad pointer")
        }

        off := (v - mheap_.arena_start) / ptrSize // word offset
        if off%(ptrSize*wordsPerBitmapByte) != 0 {
                gothrow("markspan: unaligned pointer")
        }

        b := mheap_.arena_start - off/wordsPerBitmapByte - 1
        n /= ptrSize
        if n%(ptrSize*wordsPerBitmapByte) != 0 {
                gothrow("unmarkspan: unaligned length")
        }

        // Okay to use non-atomic ops here, because we control
        // the entire span, and each bitmap word has bits for only
        // one span, so no other goroutines are changing these
        // bitmap words.
        n /= wordsPerBitmapByte
        memclr(unsafe.Pointer(b-n+1), n)
}

func mHeap_MapBits(h *mheap) {
        // Caller has added extra mappings to the arena.
        // Add extra mappings of bitmap words as needed.
        // We allocate extra bitmap pieces in chunks of bitmapChunk.
        const bitmapChunk = 8192

        n := (h.arena_used - h.arena_start) / (ptrSize * wordsPerBitmapByte)
        n = round(n, bitmapChunk)
        n = round(n, _PhysPageSize)
        if h.bitmap_mapped >= n {
                return
        }

        sysMap(unsafe.Pointer(h.arena_start-n), n-h.bitmap_mapped, h.arena_reserved, &memstats.gc_sys)
        h.bitmap_mapped = n
}

func getgcmaskcb(frame *stkframe, ctxt unsafe.Pointer) bool {
        target := (*stkframe)(ctxt)
        if frame.sp <= target.sp && target.sp < frame.varp {
                *target = *frame
                return false
        }
        return true
}

// Returns GC type info for object p for testing.
func getgcmask(p unsafe.Pointer, t *_type, mask **byte, len *uintptr) {
        *mask = nil
        *len = 0

        // data
        if uintptr(unsafe.Pointer(&data)) <= uintptr(p) && uintptr(p) < uintptr(unsafe.Pointer(&edata)) {
                n := (*ptrtype)(unsafe.Pointer(t)).elem.size
                *len = n / ptrSize
                *mask = &make([]byte, *len)[0]
                for i := uintptr(0); i < n; i += ptrSize {
                        off := (uintptr(p) + i - uintptr(unsafe.Pointer(&data))) / ptrSize
                        bits := (*(*byte)(add(unsafe.Pointer(gcdatamask.bytedata), off/pointersPerByte)) >> ((off % pointersPerByte) * bitsPerPointer)) & bitsMask
                        *(*byte)(add(unsafe.Pointer(*mask), i/ptrSize)) = bits
                }
                return
        }

        // bss
        if uintptr(unsafe.Pointer(&bss)) <= uintptr(p) && uintptr(p) < uintptr(unsafe.Pointer(&ebss)) {
                n := (*ptrtype)(unsafe.Pointer(t)).elem.size
                *len = n / ptrSize
                *mask = &make([]byte, *len)[0]
                for i := uintptr(0); i < n; i += ptrSize {
                        off := (uintptr(p) + i - uintptr(unsafe.Pointer(&bss))) / ptrSize
                        bits := (*(*byte)(add(unsafe.Pointer(gcbssmask.bytedata), off/pointersPerByte)) >> ((off % pointersPerByte) * bitsPerPointer)) & bitsMask
                        *(*byte)(add(unsafe.Pointer(*mask), i/ptrSize)) = bits
                }
                return
        }

        // heap
        var n uintptr
        var base uintptr
        if mlookup(uintptr(p), &base, &n, nil) != 0 {
                *len = n / ptrSize
                *mask = &make([]byte, *len)[0]
                for i := uintptr(0); i < n; i += ptrSize {
                        off := (uintptr(base) + i - mheap_.arena_start) / ptrSize
                        b := mheap_.arena_start - off/wordsPerBitmapByte - 1
                        shift := (off % wordsPerBitmapByte) * gcBits
                        bits := (*(*byte)(unsafe.Pointer(b)) >> (shift + 2)) & bitsMask
                        *(*byte)(add(unsafe.Pointer(*mask), i/ptrSize)) = bits
                }
                return
        }

        // stack
        var frame stkframe
        frame.sp = uintptr(p)
        _g_ := getg()
        gentraceback(_g_.m.curg.sched.pc, _g_.m.curg.sched.sp, 0, _g_.m.curg, 0, nil, 1000, getgcmaskcb, noescape(unsafe.Pointer(&frame)), 0)
        if frame.fn != nil {
                f := frame.fn
                targetpc := frame.continpc
                if targetpc == 0 {
                        return
                }
                if targetpc != f.entry {
                        targetpc--
                }
                pcdata := pcdatavalue(f, _PCDATA_StackMapIndex, targetpc)
                if pcdata == -1 {
                        return
                }
                stkmap := (*stackmap)(funcdata(f, _FUNCDATA_LocalsPointerMaps))
                if stkmap == nil || stkmap.n <= 0 {
                        return
                }
                bv := stackmapdata(stkmap, pcdata)
                size := uintptr(bv.n) / bitsPerPointer * ptrSize
                n := (*ptrtype)(unsafe.Pointer(t)).elem.size
                *len = n / ptrSize
                *mask = &make([]byte, *len)[0]
                for i := uintptr(0); i < n; i += ptrSize {
                        off := (uintptr(p) + i - frame.varp + size) / ptrSize
                        bits := ((*(*byte)(add(unsafe.Pointer(bv.bytedata), off*bitsPerPointer/8))) >> ((off * bitsPerPointer) % 8)) & bitsMask
                        *(*byte)(add(unsafe.Pointer(*mask), i/ptrSize)) = bits
                }
        }
}

func unixnanotime() int64 {
        var now int64
        gc_unixnanotime(&now)
        return now
}