// 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. // Garbage collector: sweeping package runtime import "unsafe" var sweep sweepdata // State of background sweep. type sweepdata struct { lock mutex g *g parked bool started bool spanidx uint32 // background sweeper position nbgsweep uint32 npausesweep uint32 } //go:nowritebarrier 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) } } } func bgsweep(c chan int) { sweep.g = getg() lock(&sweep.lock) sweep.parked = true c <- 1 goparkunlock(&sweep.lock, "GC sweep wait", traceEvGoBlock, 1) for { for gosweepone() != ^uintptr(0) { sweep.nbgsweep++ Gosched() } lock(&sweep.lock) if !gosweepdone() { // This can happen if a GC runs between // gosweepone returning ^0 above // and the lock being acquired. unlock(&sweep.lock) continue } sweep.parked = true goparkunlock(&sweep.lock, "GC sweep wait", traceEvGoBlock, 1) } } // sweeps one span // returns number of pages returned to heap, or ^uintptr(0) if there is nothing to sweep //go:nowritebarrier 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 } } //go:nowritebarrier func gosweepone() uintptr { var ret uintptr systemstack(func() { ret = sweepone() }) return ret } //go:nowritebarrier func gosweepdone() bool { return mheap_.sweepdone != 0 } // Returns only when span s has been swept. //go:nowritebarrier 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 { throw("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. //TODO go:nowritebarrier func mSpan_Sweep(s *mspan, preserve bool) bool { // 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 { throw("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") throw("MSpan_Sweep: bad span state") } if trace.enabled { traceGCSweepStart() } xadd64(&mheap_.pagesSwept, int64(s.npages)) cl := s.sizeclass size := s.elemsize res := false nfree := 0 var head, end gclinkptr c := _g_.m.mcache freeToHeap := false // Mark any free objects in this span so we don't collect them. sstart := uintptr(s.start << _PageShift) for link := s.freelist; link.ptr() != nil; link = link.ptr().next { if uintptr(link) < sstart || s.limit <= uintptr(link) { // Free list is corrupted. dumpFreeList(s) throw("free list corrupted") } heapBitsForAddr(uintptr(link)).setMarkedNonAtomic() } // 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 hbits := heapBitsForAddr(p) if !hbits.isMarked() { // 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 hbits.setMarkedNonAtomic() } } 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. size, n, _ := s.layout() heapBitsSweepSpan(s.base(), size, n, func(p uintptr) { // 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. if cl == 0 { // Free large span. if preserve { throw("can't preserve large span") } heapBitsForSpan(p).initSpan(s.layout()) s.needzero = 1 // important to set sweepgen before returning it to heap atomicstore(&s.sweepgen, sweepgen) // Free the span after heapBitsSweepSpan // returns, since it's not done with the span. freeToHeap = 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 } if head.ptr() == nil { head = gclinkptr(p) } else { end.ptr().next = gclinkptr(p) } end = gclinkptr(p) end.ptr().next = gclinkptr(0x0bade5) 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. // // TODO(austin): Clean this up by consolidating atomicstore in // large span path above with this. if !freeToHeap && 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") throw("MSpan_Sweep: bad span state after sweep") } atomicstore(&s.sweepgen, sweepgen) } if nfree > 0 { c.local_nsmallfree[cl] += uintptr(nfree) res = mCentral_FreeSpan(&mheap_.central[cl].mcentral, s, int32(nfree), head, end, preserve) // MCentral_FreeSpan updates sweepgen } else if freeToHeap { // Free large span to heap // 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(uintptr(s.start<<_PageShift)), size) } else { mHeap_Free(&mheap_, s, 1) } c.local_nlargefree++ c.local_largefree += size res = true } if trace.enabled { traceGCSweepDone() } return res } // deductSweepCredit deducts sweep credit for allocating a span of // size spanBytes. This must be performed *before* the span is // allocated to ensure the system has enough credit. If necessary, it // performs sweeping to prevent going in to debt. If the caller will // also sweep pages (e.g., for a large allocation), it can pass a // non-zero callerSweepPages to leave that many pages unswept. // // deductSweepCredit is the core of the "proportional sweep" system. // It uses statistics gathered by the garbage collector to perform // enough sweeping so that all pages are swept during the concurrent // sweep phase between GC cycles. // // mheap_ must NOT be locked. func deductSweepCredit(spanBytes uintptr, callerSweepPages uintptr) { if mheap_.sweepPagesPerByte == 0 { // Proportional sweep is done or disabled. return } // Account for this span allocation. spanBytesAlloc := xadd64(&mheap_.spanBytesAlloc, int64(spanBytes)) // Fix debt if necessary. pagesOwed := int64(mheap_.sweepPagesPerByte * float64(spanBytesAlloc)) for pagesOwed-int64(atomicload64(&mheap_.pagesSwept)) > int64(callerSweepPages) { if gosweepone() == ^uintptr(0) { mheap_.sweepPagesPerByte = 0 break } } } func dumpFreeList(s *mspan) { printlock() print("runtime: free list of span ", s, ":\n") sstart := uintptr(s.start << _PageShift) link := s.freelist for i := 0; i < int(s.npages*_PageSize/s.elemsize); i++ { if i != 0 { print(" -> ") } print(hex(link)) if link.ptr() == nil { break } if uintptr(link) < sstart || s.limit <= uintptr(link) { // Bad link. Stop walking before we crash. print(" (BAD)") break } link = link.ptr().next } print("\n") printunlock() }